License
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://drops.dagstuhl.de/opus/volltexte/2009/2339/

Ravi, R.

Iterative Methods in Combinatorial Optimization

pdf-format:
Dokument 1.pdf (129 KB)


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 =		{http://dx.doi.org/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
Seminar: 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 Published by LZI