1 Search Results for "Goyal, Keshav"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2015.10

Robust Reoptimization of Steiner Trees

Authors: Keshav Goyal and Tobias Mömke

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract

In reoptimization problems, one is given an optimal solution to a problem instance and a local modification of the instance. The goal is to obtain a solution for the modified instance. The additional information about the instance provided by the given solution plays a central role: we aim to use that information in order to obtain better solutions than we are able to compute from scratch. In this paper, we consider Steiner tree reoptimization and address the optimality requirement of the provided solution. Instead of assuming that we are provided an optimal solution, we relax the assumption to the more realistic scenario where we are given an approximate solution with an upper bound on its performance guarantee. We show that for Steiner tree reoptimization there is a clear separation between local modifications where optimality is crucial for obtaining improved approximations and those instances where approximate solutions are acceptable starting points. For some of the local modifications that have been considered in previous research, we show that for every fixed epsilon > 0, approximating the reoptimization problem with respect to a given (1+epsilon)-approximation is as hard as approximating the Steiner tree problem itself (whereas with a given optimal solution to the original problem it is known that one can obtain considerably improved results). Furthermore, we provide a new algorithmic technique that, with some further insights, allows us to obtain improved performance guarantees for Steiner tree reoptimization with respect to all remaining local modifications that have been considered in the literature: a required node of degree more than one becomes a Steiner node; a Steiner node becomes a required node; the cost of one edge is increased.

Cite as

Keshav Goyal and Tobias Mömke. Robust Reoptimization of Steiner Trees. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 10-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.FSTTCS.2015.10,
  author =	{Goyal, Keshav and M\"{o}mke, Tobias},
  title =	{{Robust Reoptimization of Steiner Trees}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{10--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.10},
  URN =		{urn:nbn:de:0030-drops-56251},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.10},
  annote =	{Keywords: reoptimization, approximation algorithms, Steiner tree problem, robustness}
}

Refine by Author
1 Goyal, Keshav
1 Mömke, Tobias

Refine by Classification

Refine by Keyword
1 Steiner tree problem
1 approximation algorithms
1 reoptimization
1 robustness

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Goyal, Keshav"

Robust Reoptimization of Steiner Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message