Approximating Incremental Combinatorial Optimization Problems.
Approximating Incremental Combinatorial Optimization Problems.
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.
- Massachusetts Institute of Technology United States
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
- Leibniz Association Germany
stable sets, matching, integral polytopes, incremental problems, matroid intersection, Approximation algorithm, matching, incremental problems, matroid intersection, integral polytopes, stable sets, Approximation algorithm, 004, 510, ddc: ddc:004
stable sets, matching, integral polytopes, incremental problems, matroid intersection, Approximation algorithm, matching, incremental problems, matroid intersection, integral polytopes, stable sets, Approximation algorithm, 004, 510, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!