Approximation algorithms for network design in non-uniform fault models
C Chekuri, R Jain - arXiv preprint arXiv:2403.15547, 2024 - arxiv.org
The Survivable Network Design problem (SNDP) is a well-studied problem, motivated by the
design of networks that are robust to faults under the assumption that any subset of edges …
design of networks that are robust to faults under the assumption that any subset of edges …
Polynomial integrality gap of flow lp for directed steiner tree
S Li, B Laekhanukit - ACM Transactions on Algorithms, 2024 - dl.acm.org
In the Directed Steiner Tree (DST) problem, we are given a directed graph on vertices with
edge-costs, a root vertex, and a set of terminals. The goal is to find a minimum-cost …
edge-costs, a root vertex, and a set of terminals. The goal is to find a minimum-cost …
Beyond tree embeddings–a deterministic framework for network design with deadlines or delay
We consider network design problems with deadline or delay. All previous results for these
models are based on randomized embedding of the graph into a tree (HST) and then …
models are based on randomized embedding of the graph into a tree (HST) and then …
Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
R Ghuge, V Nagarajan - Mathematics of Operations …, 2022 - pubsonline.informs.org
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 …
metric (V, c), root r∈ V, monotone submodular function f: 2 V→ R+, and budget B. The goal …
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2
The Steiner tree problem is one of the most prominent problems in network design. Given an
edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to …
edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to …
Truthful mechanisms for steiner tree problems
Consider an undirected graph G=(V, E) model for a communication network, where each
edge is owned by a selfish agent, who reports the cost for offering the use of her edge. Note …
edge is owned by a selfish agent, who reports the cost for offering the use of her edge. Note …
Parameterized approximation algorithms for bidirected steiner network problems
The Directed Steiner Network (DSN) problem takes as input a directed graph G=(V, E) with
non-negative edge-weights and a set D⊆ V× V of k demand pairs. The aim is to compute the …
non-negative edge-weights and a set D⊆ V× V of k demand pairs. The aim is to compute the …
A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
C Chekuri, R Jain - arXiv preprint arXiv:2410.17403, 2024 - arxiv.org
We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The
input to DSF is a directed edge-weighted graph $ G=(V, E) $ and a collection of vertex pairs …
input to DSF is a directed edge-weighted graph $ G=(V, E) $ and a collection of vertex pairs …
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph $
G=(V, E) $, a root vertex $ r $ and a set $ S\subseteq V $ of $ k $ terminals. The goal is to …
G=(V, E) $, a root vertex $ r $ and a set $ S\subseteq V $ of $ k $ terminals. The goal is to …
Towards PTAS for precedence constrained scheduling via combinatorial algorithms
S Li - Proceedings of the 2021 ACM-SIAM Symposium on …, 2021 - SIAM
We study the classic problem of scheduling n precedence constrained unit-size jobs on m=
O (1) machines so as to minimize the makespan. In a recent breakthrough, Levey and …
O (1) machines so as to minimize the makespan. In a recent breakthrough, Levey and …