Online weighted degree-bounded Steiner networks via novel online mixed packing/covering

Sina Dehghani, Soheil Ehsani, Mohammad Hajiaghayi, Vahid Liaghat, Harald Räcke, Saeed Seddighin

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

3 Zitate (Scopus)

Abstract

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF, we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance, we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal, we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting, edgeweighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately, the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In particular, it is not known whether the fractional solution obtained by standard primal-dual techniques for mixed packing/covering LPs can be rounded online. In contrast, in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. As mentioned above, we demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k logm) for the mixed packing/covering integer programs. We prove the tightness of our result by providing a matching lower bound for any randomized algorithm. We note that our solution solely depends on m and k. Indeed, there can be exponentially many variables. Furthermore, our algorithm directly provides an integral solution, even if the integrality gap of the program is unbounded. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

OriginalspracheEnglisch
Titel43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Redakteure/-innenYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektronisch)9783959770132
DOIs
PublikationsstatusVeröffentlicht - 1 Aug. 2016
Veranstaltung43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italien
Dauer: 12 Juli 201615 Juli 2016

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band55
ISSN (Print)1868-8969

Konferenz

Konferenz43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Land/GebietItalien
OrtRome
Zeitraum12/07/1615/07/16

Fingerprint

Untersuchen Sie die Forschungsthemen von „Online weighted degree-bounded Steiner networks via novel online mixed packing/covering“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren