4 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…