Joseph Cheriyan

97 papers A* 16A 3B 4Journal 64Unranked 10

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