文章基本信息

标题：Approximating Incremental Combinatorial Optimization Problems
本地全文：下载
作者：Michel X. Goemans ; Francisco Unda
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：6:1-6:14
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation algorithm; matching; incremental problems; matroid intersection; integral polytopes; stable sets