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.ICALP.2020.54
URN: urn:nbn:de:0030-drops-124619
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12461/
Go to the corresponding LIPIcs Volume Portal

Ganesh, Arun ; Maggs, Bruce M. ; Panigrahi, Debmalya

Robust Algorithms for TSP and Steiner Tree

pdf-format:
LIPIcs-ICALP-2020-54.pdf (0.6 MB)

Abstract

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.

BibTeX - Entry

@InProceedings{ganesh_et_al:LIPIcs:2020:12461,
  author =	{Arun Ganesh and Bruce M. Maggs and Debmalya Panigrahi},
  title =	{{Robust Algorithms for TSP and Steiner Tree}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12461},
  URN =		{urn:nbn:de:0030-drops-124619},
  doi =		{10.4230/LIPIcs.ICALP.2020.54},
  annote =	{Keywords: Robust optimization, Steiner tree, traveling salesman problem}
}

Keywords: Robust optimization, Steiner tree, traveling salesman problem
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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