Joseph Cheriyan

Publication Activity (10 Years)

Years Active: 1988-2024
Publications (10 Years): 26

Top Topics

Approximation Algorithms

Travelling Salesman

Graph Connectivity

Top Venues

Oper. Res. Lett.

SIAM J. Discret. Math.

Publications

Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
Approximation algorithms for flexible graph connectivity. Math. Program. 204 (1) (2024)
Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. Algorithmica 86 (8) (2024)
Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung
Unconstrained traveling tournament problem is APX-complete. Oper. Res. Lett. 51 (4) (2023)
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs. Oper. Res. Lett. 51 (3) (2023)
Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. ICALP (2023)
Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu
An Improved Approximation Algorithm for the Matching Augmentation Problem. SIAM J. Discret. Math. 37 (1) (2023)
Joseph Cheriyan, Sepehr Hajebi, Zishen Qu, Sophie Spirkl
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs. Discret. Math. 345 (7) (2022)
Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur
Approximating (p, 2) flexible graph connectivity via the primal-dual method. CoRR (2022)
Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang
A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. SIAM J. Discret. Math. 36 (3) (2022)
Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur
Extensions of the (p, q)-Flexible-Graph-Connectivity model. CoRR (2022)
Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung
Unconstrained Traveling Tournament Problem is APX-complete. CoRR (2022)
Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
Approximation Algorithms for Flexible Graph Connectivity. CoRR (2022)
Joseph Cheriyan, R. Ravi, Martin Skutella
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs. Oper. Res. Lett. 49 (6) (2021)
Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu
An Improved Approximation Algorithm for the Matching Augmentation Problem. ISAAC (2021)
Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
Approximation Algorithms for Flexible Graph Connectivity. FSTTCS (2021)
Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
A 2-Approximation Algorithm for Flexible Graph Connectivity. CoRR (2021)
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs. CoRR (2021)
Joseph Cheriyan, R. Ravi, Martin Skutella
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs. CoRR (2021)
Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu
An Improved Approximation Algorithm for the Matching Augmentation Problem. CoRR (2020)
Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. CoRR (2020)
Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. APPROX-RANDOM (2020)
Joseph Cheriyan, Zhihan Gao
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. Algorithmica 80 (2) (2018)
Joseph Cheriyan, Zhihan Gao
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica 80 (2) (2018)
Maxwell Levit, L. Sunil Chandran, Joseph Cheriyan
On Eulerian orientations of even-degree hypercubes. Oper. Res. Lett. 46 (5) (2018)
Joseph Cheriyan, Zhihan Gao
Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP). CoRR (2016)
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy. Math. Program. 159 (1-2) (2016)
Joseph Cheriyan, Zachary Friggstad, Zhihan Gao
Approximating Minimum-Cost Connected T-Joins. Algorithmica 72 (1) (2015)
Joseph Cheriyan, Zhihan Gao
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. CoRR (2015)
Joseph Cheriyan, Zhihan Gao
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. CoRR (2015)
Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. SIAM J. Comput. 43 (4) (2014)
Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti
Packing of rigid spanning subgraphs and spanning trees. J. Comb. Theory, Ser. B 105 (2014)
Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
Approximating Rooted Steiner Networks. ACM Trans. Algorithms 11 (2) (2014)
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. CoRR (2014)
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. ICALP (1) (2013)
Joseph Cheriyan, Bundit Laekhanukit
Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs. SIAM J. Discret. Math. 27 (3) (2013)
Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. FOCS (2013)
Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit
A bad example for the iterative rounding method for mincost k-connected spanning subgraphs. Discret. Optim. 10 (1) (2013)
Andrei V. Kotlov, Joseph Cheriyan
On the maximum size of a minimal k-edge connected augmentation. J. Comb. Theory, Ser. B 102 (1) (2012)
Joseph Cheriyan, Chenglong Zou
On orienting graphs for connectivity: Projective planes and Halin graphs. Oper. Res. Lett. 40 (5) (2012)
Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. Algorithmica 63 (1-2) (2012)
Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta
Approximating rooted Steiner networks. SODA (2012)
Joseph Cheriyan, Zachary Friggstad, Zhihan Gao
Approximating Minimum-Cost Connected T-Joins. APPROX-RANDOM (2012)
Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs CoRR (2012)
Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti
Packing of Rigid Spanning Subgraphs and Spanning Trees CoRR (2012)
Joseph Cheriyan, Zachary Friggstad, Zhihan Gao
Approximating Minimum-Cost Connected T-Joins CoRR (2012)
Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. APPROX-RANDOM (2009)
Joseph Cheriyan, Howard J. Karloff, Rohit Khandekar, Jochen Könemann
On the integrality ratio for tree augmentation. Oper. Res. Lett. 36 (4) (2008)
Joseph Cheriyan, Adrian Vetta
Approximation Algorithms for Network Design with Metric Costs. SIAM J. Discret. Math. 21 (3) (2007)
Joseph Cheriyan, Mohammad R. Salavatipour
Packing element-disjoint steiner trees. ACM Trans. Algorithms 3 (4) (2007)
Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta
Network Design Via Iterative Rounding Of Setpair Relaxations. Comb. 26 (3) (2006)
Joseph Cheriyan, Mohammad R. Salavatipour
Hardness and Approximation Results for Packing Steiner Trees. Algorithmica 45 (1) (2006)
Marcelo Henriques de Carvalho, Joseph Cheriyan
An O(VE) algorithm for ear decompositions of matching-covered graphs. SODA (2005)
Joseph Cheriyan, Mohammad R. Salavatipour
Packing Element-Disjoint Steiner Trees. APPROX-RANDOM (2005)
Joseph Cheriyan, Adrian Vetta
Approximation algorithms for network design with metric costs. STOC (2005)
Joseph Cheriyan, Howard J. Karloff, Yuval Rabani
Approximating Directed Multicuts. Comb. 25 (3) (2005)
Marcelo Henriques de Carvalho, Joseph Cheriyan
) algorithm for ear decompositions of matching-covered graphs. ACM Trans. Algorithms 1 (2) (2005)
Joseph Cheriyan, Mohammad R. Salavatipour
Hardness and Approximation Results for Packing Steiner Trees. ESA (2004)
Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta
An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph. SIAM J. Comput. 32 (4) (2003)
Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta
Approximation algorithms for minimum-cost k-vertex connected subgraphs. STOC (2002)
Joseph Cheriyan, Tibor Jordán, Zeev Nutov
On Rooted Node-Connectivity Problems. Algorithmica 30 (3) (2001)
Joseph Cheriyan, Howard J. Karloff, Yuval Rabani
Approximating Directed Multicuts. FOCS (2001)
F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian
Approximating the Single-Sink Link-Installation Problem in Network Design. SIAM J. Optim. 11 (3) (2001)
Joseph Cheriyan, Santosh S. Vempala
Edge Covers of Setpairs and the Iterative Rounding Method. IPCO (2001)
Joseph Cheriyan, András Sebö, Zoltán Szigeti
Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph. SIAM J. Discret. Math. 14 (2) (2001)
Joseph Cheriyan, Ramakrishna Thurimella
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. SIAM J. Comput. 30 (2) (2000)
Joseph Cheriyan, Kurt Mehlhorn
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow. Inf. Process. Lett. 69 (5) (1999)
Joseph Cheriyan, Tibor Jordán, R. Ravi
On 2-Coverings and 2-Packings of Laminar Families. ESA (1999)
Joseph Cheriyan, Ramakrishna Thurimella
Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation. J. Algorithms 33 (1) (1999)
Joseph Cheriyan, András Sebö, Zoltán Szigeti
An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. IPCO (1998)
Joseph Cheriyan, Ramakrishna Thurimella
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching Electron. Colloquium Comput. Complex. 5 (25) (1998)
Joseph Cheriyan, Tibor Jordán, Zeev Nutov
-outconnected Subgraph Problems. APPROX (1998)
Bo Yu, Joseph Cheriyan
The node multiterminal cut polyhedron. Networks 30 (2) (1997)
F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian
Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem. SODA (1997)
Joseph Cheriyan
Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory. SIAM J. Comput. 26 (6) (1997)
Bo Yu, Joseph Cheriyan, Penny E. Haxell
Hypercubes and Multicommodity Flows. SIAM J. Discret. Math. 10 (2) (1997)
Joseph Cheriyan, Ramakrishna Thurimella
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). FOCS (1996)
Joseph Cheriyan, Kurt Mehlhorn
Algorithms for Dense Graphs and Networks on the Random Access Computer. Algorithmica 15 (6) (1996)
Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn
An o(n³)-Time Algorithm Maximum-Flow Algorithm. SIAM J. Comput. 25 (6) (1996)
Joseph Cheriyan, Ramakrishna Thurimella
-Node Connectivity Augmentation (Extended Abstract). STOC (1996)
Bo Yu, Joseph Cheriyan
Approximation Algorithms for Feasible Cut and Multicut Problems. ESA (1995)
Joseph Cheriyan, Torben Hagerup
A Randomized Maximum-Flow Algorithm. SIAM J. Comput. 24 (2) (1995)
Joseph Cheriyan
) Algorithm for the Cardinality of a Maximum Matching. SODA (1994)
Joseph Cheriyan, John H. Reif
-Vertex Connectivity. Comb. 14 (4) (1994)
Joseph Cheriyan, Ming-Yang Kao, Ramakrishna Thurimella
Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity. SIAM J. Comput. 22 (1) (1993)
Joseph Cheriyan
Random Weighted Laplacians, Lovász Minimum Digraphs and Finding Minimum Separators. SODA (1993)
Joseph Cheriyan, William H. Cunningham, Levent Tunçel, Yaoguang Wang
A linear programming and rounding approach to max 2-sat. Cliques, Coloring, and Satisfiability (1993)
Joseph Cheriyan, John H. Reif
Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems. SPAA (1993)
Joseph Cheriyan, John H. Reif
-Vertex Connectivity. SODA (1992)
Robert G. Bland, Joseph Cheriyan, David L. Jensen, Laszlo Ladányi
An Empirical Study of Min Cost Flow Algorithms for the Minimum-Cost Flow Problem. Network Flows And Matching (1991)
Joseph Cheriyan, Ramakrishna Thurimella
Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract) STOC (1991)
Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn
Can A Maximum Flow be Computed on o(nm) Time? ICALP (1990)
Joseph Cheriyan, S. N. Maheshwari
Analysis of Preflow Push Algorithms for Maximum Network Flow. SIAM J. Comput. 18 (6) (1989)
Joseph Cheriyan, Torben Hagerup
A Randomized Maximum-Flow Algorithm FOCS (1989)
Joseph Cheriyan, S. N. Maheshwari
The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network. Inf. Process. Lett. 31 (3) (1989)
Joseph Cheriyan, S. N. Maheshwari
Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs. J. Algorithms 9 (4) (1988)
Joseph Cheriyan, S. N. Maheshwari
Analysis of Preflow Push Algorithms for Maximum Network Flow. FSTTCS (1988)