Joseph Cheriyan

Orcid: 0000-0003-0316-7650

Affiliations:
  • University of Waterloo, Department of Combinatorics and Optimization


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Approximation algorithms for flexible graph connectivity.
Math. Program., March, 2024

2023
Unconstrained traveling tournament problem is APX-complete.
Oper. Res. Lett., July, 2023

On a partition LP relaxation for min-cost 2-node connected spanning subgraphs.
Oper. Res. Lett., May, 2023

An Improved Approximation Algorithm for the Matching Augmentation Problem.
SIAM J. Discret. Math., March, 2023

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals.
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.
SIAM J. Discret. Math., September, 2022

Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs.
Discret. Math., 2022

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

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

2021
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs.
Oper. Res. Lett., 2021

A 2-Approximation Algorithm for Flexible Graph Connectivity.
CoRR, 2021

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

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

2018
On Eulerian orientations of even-degree hypercubes.
Oper. Res. Lett., 2018

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

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

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

2016
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy.
Math. Program., 2016

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

2015
Approximating Minimum-Cost Connected T-Joins.
Algorithmica, 2015

2014
Approximating Rooted Steiner Networks.
ACM Trans. Algorithms, 2014

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs.
SIAM J. Comput., 2014

Packing of rigid spanning subgraphs and spanning trees.
J. Comb. Theory, Ser. B, 2014

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

A bad example for the iterative rounding method for mincost k-connected spanning subgraphs.
Discret. Optim., 2013

2012
On orienting graphs for connectivity: Projective planes and Halin graphs.
Oper. Res. Lett., 2012

On the maximum size of a minimal k-edge connected augmentation.
J. Comb. Theory, Ser. B, 2012

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

2008
On the integrality ratio for tree augmentation.
Oper. Res. Lett., 2008

2007
Packing element-disjoint steiner trees.
ACM Trans. Algorithms, 2007

Approximation Algorithms for Network Design with Metric Costs.
SIAM J. Discret. Math., 2007

2006
Network Design Via Iterative Rounding Of Setpair Relaxations.
Comb., 2006

Hardness and Approximation Results for Packing Steiner Trees.
Algorithmica, 2006

2005
An <i>O</i>(<i>VE</i>) algorithm for ear decompositions of matching-covered graphs.
ACM Trans. Algorithms, 2005

Approximating Directed Multicuts.
Comb., 2005

An O(VE) algorithm for ear decompositions of matching-covered graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2003
An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.
SIAM J. Comput., 2003

2002
Approximation algorithms for minimum-cost k-vertex connected subgraphs.
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.
SIAM J. Optim., 2001

Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph.
SIAM J. Discret. Math., 2001

On Rooted Node-Connectivity Problems.
Algorithmica, 2001

Edge Covers of Setpairs and the Iterative Rounding Method.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

1999
Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation.
J. Algorithms, 1999

An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow.
Inf. Process. Lett., 1999

On 2-Coverings and 2-Packings of Laminar Families.
Proceedings of the Algorithms, 1999

1998
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
Electron. Colloquium Comput. Complex., 1998

An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

Approximating <i>k</i>-outconnected Subgraph Problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997
Hypercubes and Multicommodity Flows.
SIAM J. Discret. Math., 1997

Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory.
SIAM J. Comput., 1997

The node multiterminal cut polyhedron.
Networks, 1997

Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
An o(n³)-Time Algorithm Maximum-Flow Algorithm.
SIAM J. Comput., 1996

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

Fast Algorithms for <i>k</i>-Shredders and <i>k</i>-Node Connectivity Augmentation (Extended Abstract).
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).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
A Randomized Maximum-Flow Algorithm.
SIAM J. Comput., 1995

Approximation Algorithms for Feasible Cut and Multicut Problems.
Proceedings of the Algorithms, 1995

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

A Las Vegas O(n<sup>2.38</sup>) Algorithm for the Cardinality of a Maximum Matching.
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.
SIAM J. Comput., 1993

Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Random Weighted Laplacians, Lovász Minimum Digraphs and Finding Minimum Separators.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

A linear programming and rounding approach to max 2-sat.
Proceedings of the Cliques, 1993

1992
Directed <i>s-t</i> Bumberings, Rubber Bands, and Testing Digraph <i>k</i>-Vertex Connectivity.
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)
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.
Proceedings of the Network Flows And Matching, 1991

1990
Can A Maximum Flow be Computed on o(nm) Time?
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989
Analysis of Preflow Push Algorithms for Maximum Network Flow.
SIAM J. Comput., 1989

The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network.
Inf. Process. Lett., 1989

1988
Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs.
J. Algorithms, 1988


  Loading...