TY - GEN
T1 - Online and Approximate Network Construction from Bounded Connectivity Constraints
AU - Jansson, Jesper Andreas
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
N1 - Funding Information:
Research supported in part by VR grant 2017-03750 (Swedish Research Council).
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - The Network Construction problem, studied by Angluin et al., Hodosa et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S1, S2, … ⊆ V of connectivity constraints, the objective is to find a set E of edges such that each Si induces a connected subgraph of the graph (V, E) and the total cost of E is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O(B2log n) -competitive and O((B+ log r) log n) -competitive polynomial-time algorithms along with an Ω(B) -competitive lower bound, where B is an upper bound on the size of constraints, while r,n denote the number of constraints and the number of vertices, respectively. In the cost-uniform case, we provide an Ω(B) -competitive lower bound and an O(n(logn+logr)) -competitive upper bound with high probability, when constraints are unbounded. All our randomized competitive bounds are against an adaptive adversary, except for the last one which is against an oblivious adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint is supposed to induce a subgraph (of the constructed graph) of diameter at most d. Among other things, we provide a polynomial-time ((B2)-B+2)(B2) -approximation algorithm for the Network Construction problem with the d-diameter requirements.
AB - The Network Construction problem, studied by Angluin et al., Hodosa et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S1, S2, … ⊆ V of connectivity constraints, the objective is to find a set E of edges such that each Si induces a connected subgraph of the graph (V, E) and the total cost of E is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an O(B2log n) -competitive and O((B+ log r) log n) -competitive polynomial-time algorithms along with an Ω(B) -competitive lower bound, where B is an upper bound on the size of constraints, while r,n denote the number of constraints and the number of vertices, respectively. In the cost-uniform case, we provide an Ω(B) -competitive lower bound and an O(n(logn+logr)) -competitive upper bound with high probability, when constraints are unbounded. All our randomized competitive bounds are against an adaptive adversary, except for the last one which is against an oblivious adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint is supposed to induce a subgraph (of the constructed graph) of diameter at most d. Among other things, we provide a polynomial-time ((B2)-B+2)(B2) -approximation algorithm for the Network Construction problem with the d-diameter requirements.
KW - Approximation algorithm
KW - Connectivity
KW - Induced subgraph
KW - Network optimization
KW - Online algorithm
UR - http://www.scopus.com/inward/record.url?scp=85106145907&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-75242-2_22
DO - 10.1007/978-3-030-75242-2_22
M3 - Conference article published in proceeding or book
AN - SCOPUS:85106145907
SN - 9783030752415
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 314
EP - 325
BT - Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings
A2 - Calamoneri, Tiziana
A2 - Corò, Federico
PB - Springer Science and Business Media Deutschland GmbH
T2 - 12th International Conference on Algorithms and Complexity, CIAC 2021
Y2 - 10 May 2021 through 12 May 2021
ER -