From the 1 of 8 linked papers with an AI index.
8 papers · 1 filter
Length-Constrained Network Design in Planar Digraphs
Chandra Chekuri, Rhea Jain
The paper develops polylogarithmic bicriteria approximation algorithms for length-constrained versions of Directed Steiner Tree and Directed Steiner Forest in planar directed graph…
Node-Weighted Multicut in Planar Digraphs
Chandra Chekuri, Rhea Jain
Kawarabayashi and Sidiropoulos [KS22] obtained an -approximation algorithm for Multicut in planar digraphs via a natural LP relaxation, which also establishes a corres…
Streaming Algorithms for Network Design
Chandra Chekuri, Rhea Jain, Sepideh Mahabadi +1
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph and an integer…
A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
Chandra Chekuri, Rhea Jain
We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is a directed edge-weighted graph and a collection of vertex pairs…
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
Chandra Chekuri, Rhea Jain, Shubhang Kulkarni +2
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph , a root vertex and a set of terminals. The goal is to find…
Exponential Time Approximation for Coloring 3-Colorable Graphs
Venkatesan Guruswami, Rhea Jain
The problem of efficiently coloring -colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential t…