Approximating Incremental Combinatorial Optimization Problems

Authors Michel X. Goemans, Francisco Unda



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.6.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Michel X. Goemans
Francisco Unda

Cite AsGet 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.
Keywords
  • Approximation algorithm
  • matching
  • incremental problems
  • matroid intersection
  • integral polytopes
  • stable sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail