2026-07-22T05:24:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7555 2024-03-06T10:40:36Z ddc:004 open_access

Approximating Incremental Combinatorial Optimization Problems Goemans, Michel X. Unda, Francisco Approximation algorithm matching incremental problems matroid intersection integral polytopes stable sets 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michel X. Goemans and Francisco Unda 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.6 urn:nbn:de:0030-drops-75559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.6 eng https://creativecommons.org/licenses/by/3.0/legalcode