5 papers
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…
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…
Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity
Miles Simmons, Ishan Bansal, Joe Cheriyan
Diestel, et al. (see Order 35 (2017), JCT-A 167 (2019), arXiv:1805.01439) introduced the notion of abstract separation systems that satisfy a submodularity property, and they call…
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…
A Global Analysis of the Primal-Dual Method for Pliable Families
Ishan Bansal
We study a core algorithmic problem in network design called -augmentation that involves increasing the connectivity of a given family of cuts . Over 30 years ago, Willia…