12 citations · 30 across the 17 of their papers we have counts for
19 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…
Unconstrained Traveling Tournament Problem is APX-complete
Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung
We show that the Unconstrained Traveling Tournament Problem (UTTP) is APX-complete by presenting an L-reduction from a version of metric (1,2)-TSP to UTTP. Keywords: Traveling Tour…
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…
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
Ishan Bansal, Joseph Cheriyan, Logan Grout +1
We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via t…
Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
Ishan Bansal, Joe Cheriyan, Logan Grout +1
The -Steiner-2NCS problem is as follows: Given a constant , and an undirected connected graph , non-negative costs on , and a partition of in…
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
Our motivation is to improve on the best approximation guarantee known for the problem of finding a minimum-cost 2-node connected spanning subgraph of a given undirected graph with…
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
Joseph Cheriyan, Sepehr Hajebi, Zishen Qu +1
In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw () or a net (a fixed six-vertex graph) as an induc…
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…
On Eulerian orientations of even-degree hypercubes
Maxwell Levit, L. Sunil Chandran, Joseph Cheriyan
It is well known that \textit{every} Eulerian orientation of an Eulerian -edge connected (undirected) graph is strongly -edge connected. An important goal in the area is to…
Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: approximation for (Unweighted) TAP)
Joe Cheriyan, Zhihan Gao
We study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. We prove an approximation guarantee of () relative to an SDP relaxation, wh…
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP
Joe Cheriyan, Zhihan Gao
In Part I, we study a special case of the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. In the special case, we forbid so-called stems; these…
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II
Joe Cheriyan, Zhihan Gao
In Part II, we study the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum~of~Squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre…
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou +1
We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result…
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs
Joseph Cheriyan, Laszlo A. Vegh
We present a 6-approximation algorithm for the minimum-cost -node connected spanning subgraph problem, assuming that the number of nodes is at least . We apply a com…
Approximating Minimum-Cost Connected T-Joins
Joseph Cheriyan, Zachary Friggstad, Zhihan Gao
We design and analyse approximation algorithms for the minimum-cost connected T-join problem: given an undirected graph G = (V;E) with nonnegative costs on the edges, and a subset…
Packing of Rigid Spanning Subgraphs and Spanning Trees
Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti
We prove that every (6k + 2l, 2k)-connected simple graph contains k rigid and l connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jordán [4] and a t…