2 citations · 4 across the 6 of their papers we have counts for
8 papers · 1 filter
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…
Extensions of the -Flexible-Graph-Connectivity model
Ishan Bansal, Joseph Cheriyan, Logan Grout +1
We present approximation algorithms for network design problems in some models related to the -FGC model. Adjiashvili, Hommelsheim and Mühlenthaler introduced the model of F…
A -Approximation Algorithm for Flexible Graph Connectivity
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan +1
We present a -approximation algorithm for the Flexible Graph Connectivity problem [AHM20] via a reduction to the minimum cost -out -arborescence problem.
A -Approximation Algorithm for the Minimum -Edge Connected Multisubgraph Problem in the Half-Integral Case
S. Boyd, J. Cheriyan, R. Cummings +4
Given a connected undirected graph on vertices, and non-negative edge costs , the 2ECM problem is that of finding a -edge~connected spanning multisubgraph of $\…
An Improved Approximation Algorithm for the Matching Augmentation Problem
J. Cheriyan, R. Cummings, J. Dippel +1
We present a -approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…
The Matching Augmentation Problem: A -Approximation Algorithm
Joe Cheriyan, Jack Dippel, Fabrizio Grandoni +2
We present a approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…