Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems

Rohan Ghuge () and Viswanath Nagarajan ()
Additional contact information
Rohan Ghuge: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Viswanath Nagarajan: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1612-1630

Abstract: We consider the following general network design problem. The input is an asymmetric metric ( V , c ), root r ∈ V , monotone submodular function f : 2 V → R + , and budget B . The goal is to find an r -rooted arborescence T of cost at most B that maximizes f ( T ). Our main result is a simple quasi-polynomial time O ( log k log log k ) -approximation algorithm for this problem, in which k ≤ | V | is the number of vertices in an optimal solution. As a consequence, we obtain an O ( log 2 k log log k ) -approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved O ( log 2 k log log k ) -approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors).

Keywords: Primary: 68M10; 90C27; approximation algorithms; network design; submodularity (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1181 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:1612-1630

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().