2026-07-22T17:01:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2339 2024-03-06T10:33:19Z ddc:004 open_access

Iterative Methods in Combinatorial Optimization Ravi, R. Iterative methods combinatorial optimization network design approximation algorithms assignment problem linear programming We describe a simple iterative method for proving a variety of results in combinatorial optimization. It is inspired by Jain's iterative rounding method (FOCS 1998) for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh (STOC 2007) on designing an approximation algorithm for its degree bounded version. At the heart of the method is a counting argument that redistributes tokens from the columns to the rows of an LP extreme point. This token argument was further refined to fractional assignment and redistribution in work of Bansal, Khandekar and Nagarajan on degree-bounded directed network design (STOC 2008). In this presentation, we introduce the method using the assignment problem, describe its application to showing the integrality of Edmond's characterization (1971) of the spanning tree polyhedron, and then extend the argument to show a simple proof of the Singh and Lau's approximation algorithm (STOC 2007) for its degree constrained version, due to Bansal, Khandekar and Nagarajan. We conclude by showing how Jain's original proof can also be simplified by using a fractional token argument (joint work with Nagarajan and Singh). This presentation is extracted from an upcoming monograph on this topic co-authored with Lau and Singh. Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. Ravi 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2339 urn:nbn:de:0030-drops-23391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2339 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode