We consider the following general network design problem on directed graphs. The input is an asymmetric metric (V, c), root r in V, monotone submodular function f and budget B. The goal is to find an rrooted arborescence T of cost at most B that maximizes f(T). Our main result is a very simple quasipolynomial time approximation algorithm for this problem, where k ≤ V is the number of vertices in an optimal solution. To the best of our knowledge, this is the first nontrivial approximation ratio for this problem. As a consequence we obtain an O(log^2 k / loglogmore »
On Approximating DegreeBounded Network Design Problems
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V, E) with edge costs c ∈ ℝ_{≥ 0}^E, a root r ∈ V and k terminals K ⊆ V, we need to output a minimumcost arborescence in G that contains an rrightarrow t path for every t ∈ K. Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasipolynomial time O(log²k/log log k)approximation algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general DegreeBounded Directed Steiner Tree (DBDST) problem, where we are additionally given a degree bound d_v on each vertex v ∈ V, and we require that every vertex v in the output tree has at most d_v children. We give a quasipolynomial time (O(log n log k), O(log² n))bicriteria approximation: The algorithm produces a solution with cost at most O(log nlog k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O(log²n). This is the first nontrivial result for the problem. While our costguarantee is nearly optimal, the degree violation factor of O(log²n) is an O(log more »
 Award ID(s):
 1910565
 Publication Date:
 NSFPAR ID:
 10300267
 Journal Name:
 Leibniz international proceedings in informatics
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


We consider nodeweighted survivable network design (SNDP) in planar graphs and minorclosed families of graphs. The input consists of a nodeweighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edgeconnectivity SNDP (ECSNDP), elementconnectivity SNDP (ElemSNDP), and vertexconnectivity SNDP (VCSNDP), depending on whether the paths aremore »

Vehicle routing problems are a broad class of combinatorial optimization problems that can be formulated as the problem of finding a tour in a weighted graph that optimizes some function of the visited vertices. For instance, a canonical and extensively studied vehicle routing problem is the orienteering problem where the goal is to find a tour that maximizes the number of vertices visited by a given deadline. In this paper, we consider the computational tractability of a wellknown generalization of the orienteering problem called the OrientMTW problem. The input to OrientMTW consists of a weighted graph G(V, E) where formore »

We study the multilevel Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of nonproportional costs, this problem is hard to approximate with ratiomore »

Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set N , a weight function $$w: N \rightarrow \mathbb {R}_+$$ w : N → R + , r monotone submodular functions $$f_1,f_2,\ldots ,f_r$$ f 1 , f 2 , … , f r over N and requirements $$k_1,k_2,\ldots ,k_r$$ k 1 , k 2 , … , k r the goal is to find a minimum weight subset $$S \subseteq N$$ S ⊆ N such that $$f_i(S) \ge k_i$$ f i ( S ) ≥ k i for $$1 \le i \le r$$ 1 ≤more »