Joseph Cheriyan

According to our database, Joseph Cheriyan authored at least 72 papers between 1988 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions.

Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

Algorithmica, August, 2024

Approximation algorithms for flexible graph connectivity.

Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur

Math. Program., March, 2024

2023

Unconstrained traveling tournament problem is APX-complete.

Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung

Oper. Res. Lett., July, 2023

On a partition LP relaxation for min-cost 2-node connected spanning subgraphs.

Logan Grout, Joseph Cheriyan, Bundit Laekhanukit

Oper. Res. Lett., May, 2023

An Improved Approximation Algorithm for the Matching Augmentation Problem.

Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu

SIAM J. Discret. Math., March, 2023

Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals.

Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur

Proceedings of the Approximation, 2023

2022

A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case.

Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang

SIAM J. Discret. Math., September, 2022

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs.

Joseph Cheriyan, Sepehr Hajebi, Zishen Qu, Sophie Spirkl

Discret. Math., 2022

Extensions of the (p, q)-Flexible-Graph-Connectivity model.

Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

CoRR, 2022

Approximating (p, 2) flexible graph connectivity via the primal-dual method.

Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

CoRR, 2022

2021

A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs.

Joseph Cheriyan, R. Ravi, Martin Skutella

Oper. Res. Lett., 2021

A 2-Approximation Algorithm for Flexible Graph Connectivity.

Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur

CoRR, 2021

2020

The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm.

Joe Cheriyan, Jack Dippel, Fabrizio Grandoni, Arindam Khan, Vishnu V. Narayan

Math. Program., 2020

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case.

Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang

Proceedings of the Approximation, 2020

2018

On Eulerian orientations of even-degree hypercubes.

Maxwell Levit, L. Sunil Chandran, Joseph Cheriyan

Oper. Res. Lett., 2018

The Matching Augmentation Problem: A 7/4-Approximation Algorithm.

Joe Cheriyan, Jack Dippel, Fabrizio Grandoni, Arindam Khan, Vishnu V. Narayan

CoRR, 2018

Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II.

Joseph Cheriyan, Zhihan Gao

Algorithmica, 2018

Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP.

Joseph Cheriyan, Zhihan Gao

Algorithmica, 2018

2016

On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy.

Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla

Math. Program., 2016

Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP).

Joseph Cheriyan, Zhihan Gao

CoRR, 2016

2015

Approximating Minimum-Cost Connected T-Joins.

Joseph Cheriyan, Zachary Friggstad, Zhihan Gao

Algorithmica, 2015

2014

Approximating Rooted Steiner Networks.

Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta

ACM Trans. Algorithms, 2014

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs.

Joseph Cheriyan, László A. Végh

SIAM J. Comput., 2014

Packing of rigid spanning subgraphs and spanning trees.

Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti

J. Comb. Theory B, 2014

2013

Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs.

Joseph Cheriyan, Bundit Laekhanukit

SIAM J. Discret. Math., 2013

A bad example for the iterative rounding method for mincost k-connected spanning subgraphs.

Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit

Discret. Optim., 2013

2012

On orienting graphs for connectivity: Projective planes and Halin graphs.

Joseph Cheriyan, Chenglong Zou

Oper. Res. Lett., 2012

On the maximum size of a minimal k-edge connected augmentation.

Andrei V. Kotlov, Joseph Cheriyan

J. Comb. Theory B, 2012

Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.

Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani

Algorithmica, 2012

2008

On the integrality ratio for tree augmentation.

Joseph Cheriyan, Howard J. Karloff, Rohit Khandekar, Jochen Könemann

Oper. Res. Lett., 2008

2007

Packing element-disjoint steiner trees.

Joseph Cheriyan, Mohammad R. Salavatipour

ACM Trans. Algorithms, 2007

Approximation Algorithms for Network Design with Metric Costs.

Joseph Cheriyan, Adrian Vetta

SIAM J. Discret. Math., 2007

2006

Network Design Via Iterative Rounding Of Setpair Relaxations.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

Comb., 2006

Hardness and Approximation Results for Packing Steiner Trees.

Joseph Cheriyan, Mohammad R. Salavatipour

Algorithmica, 2006

2005

An <i>O</i>(<i>VE</i>) algorithm for ear decompositions of matching-covered graphs.

Marcelo Henriques de Carvalho, Joseph Cheriyan

ACM Trans. Algorithms, 2005

Approximating Directed Multicuts.

Joseph Cheriyan, Howard J. Karloff, Yuval Rabani

Comb., 2005

An O(VE) algorithm for ear decompositions of matching-covered graphs.

Marcelo Henriques de Carvalho, Joseph Cheriyan

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2003

An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

SIAM J. Comput., 2003

2002

Approximation algorithms for minimum-cost k-vertex connected subgraphs.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Approximating the Single-Sink Link-Installation Problem in Network Design.

F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian

SIAM J. Optim., 2001

Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph.

Joseph Cheriyan, András Sebö, Zoltán Szigeti

SIAM J. Discret. Math., 2001

On Rooted Node-Connectivity Problems.

Joseph Cheriyan, Tibor Jordán, Zeev Nutov

Algorithmica, 2001

Edge Covers of Setpairs and the Iterative Rounding Method.

Joseph Cheriyan, Santosh S. Vempala

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching.

Joseph Cheriyan, Ramakrishna Thurimella

SIAM J. Comput., 2000

1999

Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation.

Joseph Cheriyan, Ramakrishna Thurimella

J. Algorithms, 1999

An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow.

Joseph Cheriyan, Kurt Mehlhorn

Inf. Process. Lett., 1999

On 2-Coverings and 2-Packings of Laminar Families.

Joseph Cheriyan, Tibor Jordán, R. Ravi

Proceedings of the Algorithms, 1999

1998

An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs.

Joseph Cheriyan, András Sebö, Zoltán Szigeti

Proceedings of the Integer Programming and Combinatorial Optimization, 1998

Approximating <i>k</i>-outconnected Subgraph Problems.

Joseph Cheriyan, Tibor Jordán, Zeev Nutov

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Hypercubes and Multicommodity Flows.

Bo Yu, Joseph Cheriyan, Penny E. Haxell

SIAM J. Discret. Math., 1997

Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory.

Joseph Cheriyan

SIAM J. Comput., 1997

The node multiterminal cut polyhedron.

Bo Yu, Joseph Cheriyan

Networks, 1997

Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem.

F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

An o(n³)-Time Algorithm Maximum-Flow Algorithm.

Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn

SIAM J. Comput., 1996

Algorithms for Dense Graphs and Networks on the Random Access Computer.

Joseph Cheriyan, Kurt Mehlhorn

Algorithmica, 1996

Fast Algorithms for <i>k</i>-Shredders and <i>k</i>-Node Connectivity Augmentation (Extended Abstract).

Joseph Cheriyan, Ramakrishna Thurimella

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract).

Joseph Cheriyan, Ramakrishna Thurimella

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

A Randomized Maximum-Flow Algorithm.

Joseph Cheriyan, Torben Hagerup

SIAM J. Comput., 1995

Approximation Algorithms for Feasible Cut and Multicut Problems.

Bo Yu, Joseph Cheriyan

Proceedings of the Algorithms, 1995

1994

Directed <i>s-t</i> Numberings, Rubber Bands, and Testing Digraph <i>k</i>-Vertex Connectivity.

Joseph Cheriyan, John H. Reif

Comb., 1994

A Las Vegas O(n^2.38) Algorithm for the Cardinality of a Maximum Matching.

Joseph Cheriyan

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity.

Joseph Cheriyan, Ming-Yang Kao, Ramakrishna Thurimella

SIAM J. Comput., 1993

Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems.

Joseph Cheriyan, John H. Reif

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Random Weighted Laplacians, Lovász Minimum Digraphs and Finding Minimum Separators.

Joseph Cheriyan

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

A linear programming and rounding approach to max 2-sat.

Joseph Cheriyan, William H. Cunningham, Levent Tunçel, Yaoguang Wang

Proceedings of the Cliques, 1993

1992

Directed <i>s-t</i> Bumberings, Rubber Bands, and Testing Digraph <i>k</i>-Vertex Connectivity.

Joseph Cheriyan, John H. Reif

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract)

Joseph Cheriyan, Ramakrishna Thurimella

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

An Empirical Study of Min Cost Flow Algorithms for the Minimum-Cost Flow Problem.

Robert G. Bland, Joseph Cheriyan, David L. Jensen, Laszlo Ladányi

Proceedings of the Network Flows And Matching, 1991

1990

Can A Maximum Flow be Computed on o(nm) Time?

Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

Analysis of Preflow Push Algorithms for Maximum Network Flow.

Joseph Cheriyan, S. N. Maheshwari

SIAM J. Comput., 1989

The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network.

Joseph Cheriyan, S. N. Maheshwari

Inf. Process. Lett., 1989

1988

Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs.

Joseph Cheriyan, S. N. Maheshwari

J. Algorithms, 1988