License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2339
URN: urn:nbn:de:0030-drops-23391
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2339/
Go to the corresponding LIPIcs Volume Portal

Ravi, R.

Iterative Methods in Combinatorial Optimization

pdf-format:
09005.RaviR.2339.pdf (0.1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ravi:LIPIcs:2009:2339,
  author =	{R. Ravi},
  title =	{{Iterative Methods in Combinatorial Optimization}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{453--469},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2339},
  URN =		{urn:nbn:de:0030-drops-23391},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2339},
  annote =	{Keywords: Iterative methods, combinatorial optimization, network design, approximation algorithms, assignment problem, linear programming}
}

Keywords: Iterative methods, combinatorial optimization, network design, approximation algorithms, assignment problem, linear programming
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI