Text

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

We consider the following general network design problem. The input is an asymmetric metric (V, c), root r∈V, monotone submodular function f:2V→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(logkloglogk)-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(log2kloglogk)-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(log2kloglogk)-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).

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.2 May 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1612-1630

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

APPROXIMATION ALGORITHMS
NETWORK DESIGN
SUBMODULARITY

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1181

Pernyataan Tanggungjawab

Rohan Ghuge, Viswanath Nagarajan

Versi lain/terkait

Lampiran Berkas

Komentar