License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.80
URN: urn:nbn:de:0030-drops-141491
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14149/
Go to the corresponding LIPIcs Volume Portal

Huang, Chien-Chung ; Mari, Mathieu ; Mathieu, Claire ; Vygen, Jens

Approximating Maximum Integral Multiflows on Bounded Genus Graphs

pdf-format:
LIPIcs-ICALP-2021-80.pdf (0.9 MB)

Abstract

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs.ICALP.2021.80,
  author =	{Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Vygen, Jens},
  title =	{{Approximating Maximum Integral Multiflows on Bounded Genus Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{80:1--80:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14149},
  URN =		{urn:nbn:de:0030-drops-141491},
  doi =		{10.4230/LIPIcs.ICALP.2021.80},
  annote =	{Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs}
}

Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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