License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.55
URN: urn:nbn:de:0030-drops-129214
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12921/
Go to the corresponding LIPIcs Volume Portal

Garg, Naveen ; Kumar, Nikhil

Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow

pdf-format:
LIPIcs-ESA-2020-55.pdf (0.6 MB)

Abstract

Given an edge weighted graph and a forest F, the 2-edge connectivity augmentation problem is to pick a minimum weighted set of edges, E', such that every connected component of E' ∪ F is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.

BibTeX - Entry

@InProceedings{garg_et_al:LIPIcs:2020:12921,
  author =	{Naveen Garg and Nikhil Kumar},
  title =	{{Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12921},
  URN =		{urn:nbn:de:0030-drops-129214},
  doi =		{10.4230/LIPIcs.ESA.2020.55},
  annote =	{Keywords: Combinatorial Optimization, Multicommodity Flow, Network Design}
}

Keywords: Combinatorial Optimization, Multicommodity Flow, Network Design
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

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