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