Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
Ishan Bansal, Joseph Cheriyan, Sanjeev Khanna +1
We present improved approximation algorithms for some problems in the related areas of Capacitated Network Design and Flexible Graph Connectivity. In the Cap--ECSS problem, we a…
cs.DS2026
A -Approximation Analysis for the Cover Small Cuts Problem
Miles Simmons, Ishan Bansal, Joe Cheriyan
In the Cover Small Cuts problem, we are given a capacitated (undirected) graph and a threshold value , as well as a set of links with end-nodes in and a non…
cs.DS2025
A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem
Miles Simmons, Ishan Bansal, Joe Cheriyan
Jain's iterative rounding theorem is a well-known result in the area of approximation algorithms and, more broadly, in combinatorial optimization. The theorem asserts that LP relax…