Julia Chuzhoy

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths.

[BibT_eX]

[DOI]

Ruimin Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

New Hardness Results for Routing on Disjoint Paths.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.

[BibT_eX]

[DOI]

CoRR, 2022

A subpolynomial approximation algorithm for graph crossing number in low-degree graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Almost Polynomial Hardness of Node-Disjoint Paths in Grids.

[BibT_eX]

[DOI]

David Hong Kyun Kim

Theory Comput., 2021

Towards tight(er) bounds for the Excluded Grid Theorem.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2021

Decremental all-pairs shortest paths in deterministic near-linear time.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

On Packing Low-Diameter Spanning Trees.

[BibT_eX]

[DOI]

Merav Parter

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Towards Better Approximation of Graph Crossing Number.

[BibT_eX]

[DOI]

Sepideh Mahabadi

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Pinning down the Strong Wilber 1 Bound for Binary Search Trees.

[BibT_eX]

[DOI]

Parinya Chalermsook

Thatchaphol Saranurak

Proceedings of the Approximation, 2020

2019

Large Minors in Expanders.

[BibT_eX]

[DOI]

CoRR, 2019

A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Coomputer Science (FOCS 2014).

[BibT_eX]

[DOI]

Alexander Russell

SIAM J. Comput., 2017

2016

Large-Treewidth Graph Decompositions.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Generalized Steiner Network.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Approximation Algorithms and Hardness of the k-Route Cut Problem.

[BibT_eX]

[DOI]

Yury Makarychev

Aravindan Vijayaraghavan

Yuan Zhou

ACM Trans. Algorithms, 2016

Routing in Undirected Graphs with Constant Congestion.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2.

[BibT_eX]

[DOI]

Shi Li

J. ACM, 2016

Polynomial Bounds for the Grid-Minor Theorem.

[BibT_eX]

[DOI]

Chandra Chekuri

J. ACM, 2016

Improved Bounds for the Excluded Grid Theorem.

[BibT_eX]

[DOI]

CoRR, 2016

Excluded Grid Theorem: Improved and Simplified (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Improved approximation for node-disjoint paths in planar graphs.

[BibT_eX]

[DOI]

Shi Li

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On Approximating Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Alina Ene

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Excluded Grid Theorem: Improved and Simplified.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Improved Bounds for the Flat Wall Theorem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Degree-3 Treewidth Sparsifiers.

[BibT_eX]

[DOI]

Chandra Chekuri

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On Approximating Node-Disjoint Paths in Grids.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2013

Approximation Algorithms for the Directed k-Tour and k-Stroll Problems.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Algorithmica, 2013

Large-treewidth graph decompositions and applications.

[BibT_eX]

[DOI]

Chandra Chekuri

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.

[BibT_eX]

[DOI]

Theory Comput., 2012

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

[BibT_eX]

[DOI]

Shi Li

CoRR, 2012

On vertex sparsifiers with Steiner nodes.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximation algorithms and hardness of integral concurrent flow.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Approximation Algorithms and Hardness of the k-Route Cut Problem

[BibT_eX]

[DOI]

Yury Makarychev

Aravindan Vijayaraghavan

Yuan Zhou

CoRR, 2011

An algorithm for the graph crossing number problem.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

On Graph Crossing Number and Edge Planarization.

[BibT_eX]

[DOI]

Yury Makarychev

Anastasios Sidiropoulos

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.

[BibT_eX]

[DOI]

Comb., 2010

Resource Minimization for Fire Containment.

[BibT_eX]

[DOI]

Parinya Chalermsook

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Approximation Algorithms for the Directed k-Tour and k-Stroll Problems.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Proceedings of the Approximation, 2010

2009

Polynomial flow-cut gaps and hardness of directed cut problems.

[BibT_eX]

[DOI]

J. ACM, 2009

Maximum independent set of rectangles.

[BibT_eX]

[DOI]

Parinya Chalermsook

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On Allocating Goods to Maximize Fairness.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Erratum: Resource Minimization Job Scheduling.

[BibT_eX]

[DOI]

Paolo Codenotti

Proceedings of the Approximation, 2009

Resource Minimization Job Scheduling.

[BibT_eX]

[DOI]

Paolo Codenotti

Proceedings of the Approximation, 2009

2008

Generalized Steiner Network.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

On the approximability of some network design problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Network design for vertex connectivity.

[BibT_eX]

[DOI]

Tanmoy Chakraborty

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Algorithms for Single-Source Vertex Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Algorithmic aspects of bandwidth trading.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

The Hardness of Metric Labeling.

[BibT_eX]

[DOI]

Joseph Naor

SIAM J. Comput., 2007

Non-Cooperative Multicast and Facility Location Games.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2007

Hardness of routing with congestion in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Covering Problems with Hard Capacities.

[BibT_eX]

[DOI]

Joseph Naor

SIAM J. Comput., 2006

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.

[BibT_eX]

[DOI]

Rafail Ostrovsky

Yuval Rabani

Math. Oper. Res., 2006

New hardness results for congestion minimization and machine scheduling.

[BibT_eX]

[DOI]

Joseph Naor

J. ACM, 2006

Hardness of Directed Routing with Congestion.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Hardness of cut problems in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Embedding ultrametrics into low-dimensional spaces.

[BibT_eX]

[DOI]

Mihai Badoiu

Piotr Indyk

Anastasios Sidiropoulos

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Asymmetric k-center is log* n-hard to approximate.

[BibT_eX]

[DOI]

J. ACM, 2005

Low-distortion embeddings of general metrics into the line.

[BibT_eX]

[DOI]

Mihai Badoiu

Piotr Indyk

Anastasios Sidiropoulos

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximating k-median with non-uniform capacities.

[BibT_eX]

[DOI]

Yuval Rabani

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

Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Hardness approximation and new approximability classes.

[BibT_eX]

[DOI]