Abstract
We design the first online algorithm with polylogarithmic competitive ratio for the edgeweighted degreebounded Steiner forest (EWDBSF) 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 EWDBSF, we are given an edgeweighted 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 degreebounded Steiner tree (EWDBST) 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 degreebounded problems. In particular, it is not known whether the fractional solution obtained by standard primaldual 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 EWDBSF problem to an exponentialsize 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*log(m)) 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 primaldual techniques in solving online problems.
BibTeX  Entry
@InProceedings{dehghani_et_al:LIPIcs:2016:6322,
author = {Sina Dehghani and Soheil Ehsani and Mohammad Taghi Hajiaghayi and Vahid Liaghat and Harald R{\"a}cke and Saeed Seddighin},
title = {{Online Weighted DegreeBounded Steiner Networks via Novel Online Mixed Packing/Covering}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {42:142:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6322},
URN = {urn:nbn:de:0030drops63221},
doi = {10.4230/LIPIcs.ICALP.2016.42},
annote = {Keywords: Online, Steiner Tree, Approximation, Competitive ratio}
}
Keywords: 

Online, Steiner Tree, Approximation, Competitive ratio 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 