LIPIcs.APPROX-RANDOM.2017.6.pdf
- Filesize: 0.49 MB
- 14 pages
Document
Approximating Incremental Combinatorial Optimization Problems
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-08-11
Cite As Get BibTex
Michel X. Goemans and Francisco Unda. Approximating Incremental Combinatorial Optimization Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.6
Abstract
We consider incremental combinatorial optimization problems, in which a solution is constructed incrementally over time, and the goal is to optimize not the value of the final solution but the average value over all timesteps. We consider a natural algorithm of moving towards a global optimum solution as quickly as possible. We show that this algorithm provides an approximation guarantee of (9+sqrt(21))/15 > 0.9 for a large class of incremental combinatorial optimization problems defined axiomatically, which includes (bipartite and non-bipartite) matchings, matroid intersections, and stable sets in claw-free graphs. Furthermore, our analysis is tight.
Subject Classification
Keywords
- Approximation algorithm
- matching
- incremental problems
- matroid intersection
- integral polytopes
- stable sets
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. Baxter, T. Elgindy, A. T. Ernst, T. Kalinowski, and M. W. P. Savelsbergh. Incremental network design with shortest paths. European Journal of Operational Research, 242:51-62, 2015. URL: http://dx.doi.org/10.1016/j.ejor.2014.04.018.
- V. Chvátal. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B, 18:138-154, 1975. URL: http://dx.doi.org/10.1016/0095-8956(75)90041-6.
- J. Edmonds. Maximum matching and a polyhedron with 0,1 vertices. Journal of Research National Bureau of Standards, Section B69, pages 125-130, 1965. URL: http://dx.doi.org/10.6028/jres.069B.013.
- J. Edmonds. Paths, trees and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. URL: http://dx.doi.org/10.4153/CJM-1965-045-4.
- J. Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications, pages 69-87, 1970. URL: http://dx.doi.org/10.1007/3-540-36478-1_2.
- K. Engel, T. Kalinowski, and M. W. P. Savelsbergh. Incremental network design problem with spanning trees. Journal of Graph Algorithms and Applications, 2013. http://arxiv.org/abs/0902.0885, URL: http://dx.doi.org/10.7155/jgaa.00423.
- T. Kalinowski, D. Matsypura, and M. W. P. Savelsbergh. Incremental network design with maximum flows. European Journal of Combinatorial Research, 3:675-684, 2014. URL: http://dx.doi.org/10.1016/j.ejor.2014.10.003.
- G. J. Minty. On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B, 28:284-304, 1980. URL: http://dx.doi.org/10.1016/0095-8956(80)90074-X.
- S. G. Nurre and T. C. Sharkey. Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules. Networks, 63:306-326, 2014. URL: http://dx.doi.org/10.1002/net.21547.
- N. Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile. Discrete Mathematics, 29:53-76, 1980. URL: http://dx.doi.org/10.1016/0012-365X(90)90287-R.
-
A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.
