default search action
Joseph Cheriyan
Joe Cheriyan
Person information
- affiliation: University of Waterloo, Department of Combinatorics and Optimization
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j47]Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur:
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. Algorithmica 86(8): 2575-2604 (2024) - [j46]Sylvia C. Boyd, Joseph Cheriyan
, Arash Haddadan, Sharat Ibrahimpur
Approximation algorithms for flexible graph connectivity. Math. Program. 204(1): 493-516 (2024) - 2023
- [j45]Logan Grout, Joseph Cheriyan
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs. Oper. Res. Lett. 51(3): 289-295 (2023) - [j44]Salomon Bendayan, Joseph Cheriyan
Unconstrained traveling tournament problem is APX-complete. Oper. Res. Lett. 51(4): 456-460 (2023) - [j43]Joseph Cheriyan, Robert Cummings, Jack Dippel
An Improved Approximation Algorithm for the Matching Augmentation Problem. SIAM J. Discret. Math. 37(1): 163-190 (2023) - [c34]Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur:
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals. APPROX/RANDOM 2023: 14:1-14:14 - [c33]Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur:
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. ICALP 2023: 15:1-15:19 - 2022
- [j42]Joseph Cheriyan
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs. Discret. Math. 345(7): 112869 (2022) - [j41]Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur
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): 1730-1747 (2022) - [i19]Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur:
Approximation Algorithms for Flexible Graph Connectivity. CoRR abs/2202.13298 (2022) - [i18]Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur:
Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals. CoRR abs/2206.11807 (2022) - [i17]Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur
Approximating (p, 2) flexible graph connectivity via the primal-dual method. CoRR abs/2209.11209 (2022) - [i16]Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur:
Extensions of the (p, q)-Flexible-Graph-Connectivity model. CoRR abs/2211.09747 (2022) - [i15]Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung:
Unconstrained Traveling Tournament Problem is APX-complete. CoRR abs/2212.09165 (2022) - 2021
- [j40]Joseph Cheriyan, R. Ravi
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs. Oper. Res. Lett. 49(6): 842-843 (2021) - [c32]Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
Approximation Algorithms for Flexible Graph Connectivity. FSTTCS 2021: 9:1-9:14 - [c31]Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu:
An Improved Approximation Algorithm for the Matching Augmentation Problem. ISAAC 2021: 38:1-38:17 - [i14]Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, Sharat Ibrahimpur
A 2-Approximation Algorithm for Flexible Graph Connectivity. CoRR abs/2102.03304 (2021) - [i13]Joseph Cheriyan, R. Ravi, Martin Skutella:
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs. CoRR abs/2104.06210 (2021) - [i12]Logan Grout, Joseph Cheriyan, Bundit Laekhanukit:
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs. CoRR abs/2111.07481 (2021) - 2020
- [j39]Joe Cheriyan
The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm. Math. Program. 182(1): 315-354 (2020) - [c30]Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. APPROX-RANDOM 2020: 61:1-61:12 - [i11]Joseph Cheriyan, Robert Cummings, Jack Dippel, Jasper Zhu:
An Improved Approximation Algorithm for the Matching Augmentation Problem. CoRR abs/2007.11559 (2020) - [i10]Sylvia C. Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. CoRR abs/2008.03327 (2020)
2010 – 2019
- 2018
- [j38]Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica 80(2): 530-559 (2018) - [j37]Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. Algorithmica 80(2): 608-651 (2018) - [j36]Maxwell Levit, L. Sunil Chandran, Joseph Cheriyan:
On Eulerian orientations of even-degree hypercubes. Oper. Res. Lett. 46(5): 553-556 (2018) - [i9]Joe Cheriyan, Jack Dippel, Fabrizio Grandoni, Arindam Khan, Vishnu V. Narayan:
The Matching Augmentation Problem: A 7/4-Approximation Algorithm. CoRR abs/1810.07816 (2018) - 2016
- [j35]Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla:
On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy. Math. Program. 159(1-2): 1-29 (2016) - [i8]Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: $1.8+ε$ approximation for (Unweighted) TAP). CoRR abs/1604.00708 (2016) - 2015
- [j34]Joseph Cheriyan, Zachary Friggstad, Zhihan Gao:
Approximating Minimum-Cost Connected T-Joins. Algorithmica 72(1): 126-147 (2015) - [i7]Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. CoRR abs/1507.01309 (2015) - [i6]Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. CoRR abs/1508.07504 (2015) - 2014
- [j33]Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti:
Packing of rigid spanning subgraphs and spanning trees. J. Comb. Theory B 105: 17-25 (2014) - [j32]Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. SIAM J. Comput. 43(4): 1342-1362 (2014) - [j31]Joseph Cheriyan, Bundit Laekhanukit
Approximating Rooted Steiner Networks. ACM Trans. Algorithms 11(2): 8:1-8:22 (2014) - [i5]Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla:
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. CoRR abs/1405.0945 (2014) - 2013
- [j30]Ashkan Aazami, Joseph Cheriyan, Bundit Laekhanukit
A bad example for the iterative rounding method for mincost k-connected spanning subgraphs. Discret. Optim. 10(1): 25-41 (2013) - [j29]Joseph Cheriyan, Bundit Laekhanukit
Approximation Algorithms for Minimum-Cost $k\hbox{-}(S, T)$ Connected Digraphs. SIAM J. Discret. Math. 27(3): 1450-1481 (2013) - [c29]Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. FOCS 2013: 30-39 - [c28]Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla:
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. ICALP (1) 2013: 340-351 - 2012
- [j28]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): 425-456 (2012) - [j27]Andrei V. Kotlov, Joseph Cheriyan:
On the maximum size of a minimal k-edge connected augmentation. J. Comb. Theory B 102(1): 206-211 (2012) - [j26]Joseph Cheriyan, Chenglong Zou:
On orienting graphs for connectivity: Projective planes and Halin graphs. Oper. Res. Lett. 40(5): 337-341 (2012) - [c27]Joseph Cheriyan, Zachary Friggstad, Zhihan Gao:
Approximating Minimum-Cost Connected T-Joins. APPROX-RANDOM 2012: 110-121 - [c26]Joseph Cheriyan, Bundit Laekhanukit
Approximating rooted Steiner networks. SODA 2012: 1499-1511 - [i4]Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti:
Packing of Rigid Spanning Subgraphs and Spanning Trees. CoRR abs/1201.3727 (2012) - [i3]Joseph Cheriyan, Zachary Friggstad, Zhihan Gao:
Approximating Minimum-Cost Connected T-Joins. CoRR abs/1207.5722 (2012) - [i2]Joseph Cheriyan, László A. Végh:
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. CoRR abs/1212.3981 (2012)
2000 – 2009
- 2009
- [c25]Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani:
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. APPROX-RANDOM 2009: 1-14 - 2008
- [j25]Joseph Cheriyan, Howard J. Karloff, Rohit Khandekar, Jochen Könemann:
On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4): 399-401 (2008) - 2007
- [j24]Joseph Cheriyan, Adrian Vetta:
Approximation Algorithms for Network Design with Metric Costs. SIAM J. Discret. Math. 21(3): 612-636 (2007) - [j23]Joseph Cheriyan, Mohammad R. Salavatipour:
Packing element-disjoint steiner trees. ACM Trans. Algorithms 3(4): 47 (2007) - 2006
- [j22]Joseph Cheriyan, Mohammad R. Salavatipour:
Hardness and Approximation Results for Packing Steiner Trees. Algorithmica 45(1): 21-43 (2006) - [j21]Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta:
Network Design Via Iterative Rounding Of Setpair Relaxations. Comb. 26(3): 255-275 (2006) - 2005
- [j20]Joseph Cheriyan, Howard J. Karloff, Yuval Rabani
Approximating Directed Multicuts. Comb. 25(3): 251-269 (2005) - [j19]Marcelo Henriques de Carvalho, Joseph Cheriyan:
An O(VE) algorithm for ear decompositions of matching-covered graphs. ACM Trans. Algorithms 1(2): 324-337 (2005) - [c24]Joseph Cheriyan, Mohammad R. Salavatipour:
Packing Element-Disjoint Steiner Trees. APPROX-RANDOM 2005: 52-61 - [c23]Marcelo Henriques de Carvalho, Joseph Cheriyan:
An O(VE) algorithm for ear decompositions of matching-covered graphs. SODA 2005: 415-423 - [c22]Joseph Cheriyan, Adrian Vetta:
Approximation algorithms for network design with metric costs. STOC 2005: 167-175 - 2004
- [c21]Joseph Cheriyan, Mohammad R. Salavatipour:
Hardness and Approximation Results for Packing Steiner Trees. ESA 2004: 180-191 - 2003
- [j18]Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta:
An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph. SIAM J. Comput. 32(4): 1050-1055 (2003) - 2002
- [c20]Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta:
Approximation algorithms for minimum-cost k-vertex connected subgraphs. STOC 2002: 306-312 - 2001
- [j17]Joseph Cheriyan, Tibor Jordán, Zeev Nutov:
On Rooted Node-Connectivity Problems. Algorithmica 30(3): 353-375 (2001) - [j16]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): 170-180 (2001) - [j15]F. Sibel Salman
Approximating the Single-Sink Link-Installation Problem in Network Design. SIAM J. Optim. 11(3): 595-610 (2001) - [c19]Joseph Cheriyan, Howard J. Karloff, Yuval Rabani
Approximating Directed Multicuts. FOCS 2001: 320-328 - [c18]Joseph Cheriyan, Santosh S. Vempala:
Edge Covers of Setpairs and the Iterative Rounding Method. IPCO 2001: 30-44 - 2000
- [j14]Joseph Cheriyan, Ramakrishna Thurimella:
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. SIAM J. Comput. 30(2): 528-560 (2000)
1990 – 1999
- 1999
- [j13]Joseph Cheriyan, Kurt Mehlhorn:
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow. Inf. Process. Lett. 69(5): 239-242 (1999) - [j12]Joseph Cheriyan, Ramakrishna Thurimella:
Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation. J. Algorithms 33(1): 15-50 (1999) - [c17]Joseph Cheriyan, Tibor Jordán, R. Ravi:
On 2-Coverings and 2-Packings of Laminar Families. ESA 1999: 510-520 - 1998
- [c16]Joseph Cheriyan, Tibor Jordán, Zeev Nutov:
Approximating k-outconnected Subgraph Problems. APPROX 1998: 77-88 - [c15]Joseph Cheriyan, András Sebö, Zoltán Szigeti:
An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. IPCO 1998: 126-136 - [i1]Joseph Cheriyan, Ramakrishna Thurimella:
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j11]Bo Yu, Joseph Cheriyan:
The node multiterminal cut polyhedron. Networks 30(2): 133-148 (1997) - [j10]Joseph Cheriyan:
Randomized Õ(M(|V|)) Algorithms for Problems in Matching Theory. SIAM J. Comput. 26(6): 1635-1669 (1997) - [j9]Bo Yu, Joseph Cheriyan, Penny E. Haxell:
Hypercubes and Multicommodity Flows. SIAM J. Discret. Math. 10(2): 190-200 (1997) - [c14]F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian:
Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem. SODA 1997: 619-628 - 1996
- [j8]Joseph Cheriyan, Kurt Mehlhorn:
Algorithms for Dense Graphs and Networks on the Random Access Computer. Algorithmica 15(6): 521-549 (1996) - [j7]Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn:
An o(n³)-Time Algorithm Maximum-Flow Algorithm. SIAM J. Comput. 25(6): 1144-1170 (1996) - [c13]Joseph Cheriyan, Ramakrishna Thurimella:
Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). FOCS 1996: 292-301 - [c12]Joseph Cheriyan, Ramakrishna Thurimella:
Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation (Extended Abstract). STOC 1996: 37-46 - 1995
- [j6]Joseph Cheriyan, Torben Hagerup:
A Randomized Maximum-Flow Algorithm. SIAM J. Comput. 24(2): 203-226 (1995) - [c11]Bo Yu, Joseph Cheriyan:
Approximation Algorithms for Feasible Cut and Multicut Problems. ESA 1995: 394-408 - 1994
- [j5]Joseph Cheriyan, John H. Reif:
Directed s-t Numberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity. Comb. 14(4): 435-451 (1994) - [c10]Joseph Cheriyan:
A Las Vegas O(n2.38) Algorithm for the Cardinality of a Maximum Matching. SODA 1994: 442-451 - 1993
- [j4]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): 157-174 (1993) - [c9]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: 395-413 - [c8]Joseph Cheriyan:
Random Weighted Laplacians, Lovász Minimum Digraphs and Finding Minimum Separators. SODA 1993: 31-40 - [c7]Joseph Cheriyan, John H. Reif:
Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems. SPAA 1993: 50-56 - 1992
- [c6]Joseph Cheriyan, John H. Reif:
Directed s-t Bumberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity. SODA 1992: 335-344 - 1991
- [c5]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: 119-156 - [c4]Joseph Cheriyan, Ramakrishna Thurimella:
Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract). STOC 1991: 391-401 - 1990
- [c3]Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn:
Can A Maximum Flow be Computed on o(nm) Time? ICALP 1990: 235-248
1980 – 1989
- 1989
- [j3]Joseph Cheriyan, S. N. Maheshwari:
The Parallel Complexity of Finding a Blocking Flow in a 3-Layer Network. Inf. Process. Lett. 31(3): 157-161 (1989) - [j2]Joseph Cheriyan, S. N. Maheshwari:
Analysis of Preflow Push Algorithms for Maximum Network Flow. SIAM J. Comput. 18(6): 1057-1086 (1989) - [c2]Joseph Cheriyan, Torben Hagerup:
A Randomized Maximum-Flow Algorithm. FOCS 1989: 118-123 - 1988
- [j1]Joseph Cheriyan, S. N. Maheshwari:
Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs. J. Algorithms 9(4): 507-537 (1988) - [c1]Joseph Cheriyan, S. N. Maheshwari:
Analysis of Preflow Push Algorithms for Maximum Network Flow. FSTTCS 1988: 30-48
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:22 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: