# Julia Chuzhoy

According to our database

Collaborative distances:

^{1}, Julia Chuzhoy authored at least 63 papers between 2003 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

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

CoRR, 2019

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

CoRR, 2019

Large Minors in Expanders.

CoRR, 2019

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

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

Towards Tight(er) Bounds for the Excluded Grid Theorem.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Almost polynomial hardness of node-disjoint paths in grids.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

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

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).

SIAM J. Comput., 2017

New hardness results for routing on disjoint paths.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Large-Treewidth Graph Decompositions.

Encyclopedia of Algorithms, 2016

Generalized Steiner Network.

Encyclopedia of Algorithms, 2016

Approximation Algorithms and Hardness of the

*k*-Route Cut Problem.
ACM Trans. Algorithms, 2016

Routing in Undirected Graphs with Constant Congestion.

SIAM J. Comput., 2016

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

J. ACM, 2016

Polynomial Bounds for the Grid-Minor Theorem.

J. ACM, 2016

Improved Bounds for the Excluded Grid Theorem.

CoRR, 2016

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

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

Improved approximation for node-disjoint paths in planar graphs.

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

On Approximating Maximum Independent Set of Rectangles.

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

2015

Excluded Grid Theorem: Improved and Simplified.

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

Improved Bounds for the Flat Wall Theorem.

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

Degree-3 Treewidth Sparsifiers.

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

On Approximating Node-Disjoint Paths in Grids.

Proceedings of the Approximation, 2015

2013

Algorithmica, 2013

Large-treewidth graph decompositions and applications.

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

An O(k

^{3}log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
Theory of Computing, 2012

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

CoRR, 2012

On vertex sparsifiers with Steiner nodes.

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

Approximation algorithms and hardness of integral concurrent flow.

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

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

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

2011

Approximation Algorithms and Hardness of the k-Route Cut Problem

CoRR, 2011

An algorithm for the graph crossing number problem.

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

On Graph Crossing Number and Edge Planarization.

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.

Combinatorica, 2010

Resource Minimization for Fire Containment.

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

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

Proceedings of the Approximation, 2010

2009

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

J. ACM, 2009

Maximum independent set of rectangles.

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.

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

On Allocating Goods to Maximize Fairness.

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

Erratum: Resource Minimization Job Scheduling.

Proceedings of the Approximation, 2009

Resource Minimization Job Scheduling.

Proceedings of the Approximation, 2009

2008

Generalized Steiner Network.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

On the approximability of some network design problems.

ACM Trans. Algorithms, 2008

Network design for vertex connectivity.

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

Algorithms for Single-Source Vertex Connectivity.

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

2007

Algorithmic aspects of bandwidth trading.

ACM Trans. Algorithms, 2007

The Hardness of Metric Labeling.

SIAM J. Comput., 2007

Non-Cooperative Multicast and Facility Location Games.

IEEE Journal on Selected Areas in Communications, 2007

Hardness of routing with congestion in directed graphs.

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

2006

Covering Problems with Hard Capacities.

SIAM J. Comput., 2006

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

Math. Oper. Res., 2006

New hardness results for congestion minimization and machine scheduling.

J. ACM, 2006

Hardness of Directed Routing with Congestion.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Hardness of cut problems in directed graphs.

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

Embedding ultrametrics into low-dimensional spaces.

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

2005

J. ACM, 2005

Low-distortion embeddings of general metrics into the line.

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

Approximating k-median with non-uniform capacities.

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

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

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

2004

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Machine Minimization for Scheduling Jobs with Interval Constraints.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Asymmetric k-center is log

^{*}n-hard to Approximate
Electronic Colloquium on Computational Complexity (ECCC), 2003