# Corelab Seminar

*2006-2007*

### Evangelos Bampas (NTUA)

*Matroids and k-extendible systems*

**Abstract.** Our objective is to characterize classes of problems for which a greedy algorithm finds solutions provably close to optimum. To that end, we introduce the notion of k-extendible systems, a natural generalization of matroids, and show that a greedy algorithm is a 1/k-factor approximation for these systems. Many seemly unrelated problems fit in our framework, e.g.: b-matching, maximum profit scheduling and maximum asymmetric TSP.

In the second half of the paper we focus on the maximum weight b-matching problem. The problem forms a 2-extendible system, so greedy gives us a 1/2-factor solution which runs in O(mlogn) time. We improve this by providing two linear time approximation algorithms for the problem: a 1/2-factor algorithm that rungs in O(bm) time, and a (\frac{2}{3} - \epsilon)-factor algorithm which runs in expected O(bm\log(\frac{1}{\epsilon})) time.

(based on work by Julián Mestre)

**Material.** Slides [pdf].