Robust Reoptimization of Steiner Trees
- PDF / 3,455,869 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 168 Views
Robust Reoptimization of Steiner Trees Keshav Goyal1 · Tobias Mömke2 Received: 6 December 2017 / Accepted: 14 January 2020 © The Author(s) 2020
Abstract In reoptimization, one is given an optimal solution to a problem instance and a (locally) modified instance. The goal is to obtain a solution for the modified instance. We aim to use information obtained from the given solution in order to obtain a better solution for the new instance 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 𝜀 > 0 , approximating the reoptimization problem with respect to a given (1 + 𝜀)-approximation is as hard as approximating the Steiner tree problem itself. In contrast, 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. Keywords Reoptimization · Approximation algorithms · Steiner tree problem A preliminary version of this paper has appeared in Proc. 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015. * Tobias Mömke [email protected]‑saarland.de Keshav Goyal [email protected] 1
Graviton Research Capital LLP, Gurugram, Haryana, India
2
Saarland University, Saarbrücken, Germany
13
Vol.:(0123456789)
Algorithmica
1 Introduction The Steiner tree problem (STP) is one of the most studied problems in the area of network design. We are given a graph G with nodes V(G), edges E(G), and a cost function c ∶ E(G) → ℝ≥0 , as well as a set R ⊆ V(G) of required nodes (also called regular nodes or terminals). The objective is to find a minimum-cost tree T within G such that R ⊆ V(T) . The Steiner tree problem is known to be APX-hard [8], and the currently best approximation algorithm has a performance guarantee of ln 4 + 𝜀 ≈ 1.387 [25]. We consider the Steiner tree problem with respect to reoptimization, a framework for dynamic algorithms in the context of NP-hard problems. We are given two related instances I and I ′ of an algorithmic prob
Data Loading...
