Abstract
The objective of this paper 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 \(\frac{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 \(\frac{1}{2}\)-factor solution which runs in O(m logn) time. We improve this by providing two linear time approximation algorithms for the problem: a \(\frac{1}{2}\)-factor algorithm that runs in O(bm) time, and a \(\left(\frac{2}{3} -- \epsilon\right)\)-factor algorithm which runs in expected \(O\left(b m \log \frac{1}{\epsilon}\right)\) time.
Research supported by NSF Awards CCR-01-05413 and CCF-04-30650, and the University of Maryland Dean’s Dissertation Fellowship.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Angelopoulos, S., Borodin, A.: The power of priority algorithms for facility location and set cover. Algorithmica 40(4), 271–291 (2004)
Arkin, E.M., Hassin, R.: On local search for weighted k-set packing. Mathematics of Operations Research 23(3), 640–648 (1998)
Arora, V., Vempala, S., Saran, H., Vazirani, V.V.: A limited-backtrack greedy schema for approximation algorithms. In: Thiagarajan, P.S. (ed.) FSTTCS 1994. LNCS, vol. 880, pp. 318–329. Springer, Heidelberg (1994)
Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J.S., Schieber, B.: A unified approach to approximating resource allocation and scheduling. Journal of the ACM 48(5), 1069–1090 (2001)
Borodin, A., Nielsen, M.N., Rockoff, C.: (Incremental) Priority algorithms. Algorithmica 37(4), 295–326 (2003)
Borovik, A.V., Gelfand, I., White, N.: Symplectic matroid. Journal of Algebraic Combinatorics 8, 235–252 (1998)
Bouchet, A.: Greedy algorithm and symmetric matroids. Mathematical Programming 38, 147–159 (1987)
Drake, D.E., Hougardy, S.: Improved linear time approximation algorithms for weighted matchings. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 14–23. Springer, Heidelberg (2003)
Drake, D.E., Hougardy, S.: A simple approximation algorithm for the weighted matching problem. Information Processing Letters 85, 211–213 (2003)
Edmonds, J.: Minimum partition of a matroid into independent subsets. J. of Research National Bureau of Standards 69B, 67–77 (1965)
Edmonds, J.: Matroids and the greedy algorithm. Mathematical Programming 1, 36–127 (1971)
Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: STOC, pp. 448–456 (1983)
Jenkyns, T.A.: The greedy travelling salesman’s problem. Networks 9, 363–373 (1979)
Korte, B., Hausmann, D.: An analysis of the greedy algorithm for independence systems. Ann. Disc. Math. 2, 65–74 (1978)
Korte, B., Lovász, L.: Greedoids—a structural framework for the greedy algorithm. In: Progress in Combinatorial Optimization, pp. 221–243 (1984)
Lewenstein, M., Sviridenko, M.: Approximating asymmetric maximum TSP. In: SODA, pp. 646–654 (2003)
Lovász, L.: The matroid matching problem. In: Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis Janos Bolyai (1978)
Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)
Pettie, S., Sanders, P.: A simpler linear time 2/3 − ε approximation to maximum weight matching. Information Processing Letters 91(6), 271–276 (2004)
Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 259–269. Springer, Heidelberg (1999)
Rado, R.: A theorem on independence relations. Quart. J. Math. 13, 83–89 (1942)
Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)
Vince, A.: A framework for the greedy algorithm. Discrete Applied Mathematics 121(1–3), 247–260 (2002)
Whitney, H.: On the abstract properties of linear dependence. American Journal of Mathematic 57, 509–533 (1935)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mestre, J. (2006). Greedy in Approximation Algorithms. In: Azar, Y., Erlebach, T. (eds) Algorithms – ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol 4168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11841036_48
Download citation
DOI: https://doi.org/10.1007/11841036_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38875-3
Online ISBN: 978-3-540-38876-0
eBook Packages: Computer ScienceComputer Science (R0)