Julia Chuzhoy's Publications
Julia Chuzhoy's publications
 Julia Chuzhoy, David H.K. Kim and Shi Li.
Improved Approximation for NodeDisjoint Paths in Planar Graphs.
STOC 2016, to appear.
A full version, arXiv:1603.05520.
 Julia Chuzhoy.
Improved Bounds for the Excluded Grid Theorem, arxiv:1602.02629.
This paper contains a full version of the STOC 2015 paper, together with additional extensions.
The paper focuses on the "improved" aspect. I am planning to write an expository article emphasizing the "simplified" aspect.
 Julia Chuzhoy.
Excluded Grid Theorem: Improved and Simplified.
In Proc. of the 47th Annual ACM on Symposium on Theory of Computing (STOC), pages 645654, 2015.
For a full version, see this paper.
 Julia Chuzhoy and David H.K. Kim.
On Approximating NodeDisjoint Paths in Grids.
In Proc. of APPROX 2015, LIPIcsLeibniz International Proceedings in Informatics (Vol. 40).
 Chandra Chekuri and Julia Chuzhoy.
Degree3 Treewdith Sparsifiers.
In Proc. of the 26th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 242255, 2015.
A full version, arxiv:1410.1016
 Julia Chuzhoy.
Improved Bounds for the Flat Wall Theorem.
In Proc. of the 26th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pages 256275, 2015.
A full version, arxiv:1410.9276
 Chandra Chekuri and Julia Chuzhoy.
Polynomial Bounds for the GridMinor Theorem.
In Proc. of the 46th Annual Symposium on the Theory of Computing (STOC), pages 6069, 2014.
A full version, arxiv:1305.6577
 Chandra Chekuri and Julia Chuzhoy.
LargeTreewidth Graph Decompositions and Applications.
In Proc. of the 45th Annual ACM Symposium on Theory of Computing (STOC),
pages 291300, 2013.
A full version, arXiv:1304.1577.
 Julia Chuzhoy and Shi Li.
A Polylogarithimic Approximation Algorithm for EdgeDisjoint Paths with Congestion 2.
In Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 233242, 2012.
A cowinner of the FOCS 2012 Best Paper Award.
A full version, arXiv:1208.1272.
 Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan and Sanjeev Khanna.
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.
In Proc. of APPROX 2012, Lecture Notes in Computer Science 7408, pages 7384, 2012.
 Parinya Chalermsook, Julia Chuzhoy, Alina Ene and Shi Li.
Approximation Algorithms and Hardness of Integral Concurrent Flow.
In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 689708, 2012.
A full version
 Julia Chuzhoy.
On Vertex Sparsifiers with Steiner Nodes.
In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 673688, 2012.
A full version, arXiv:1204.2844.
 Julia Chuzhoy.
Routing in Undirected Graphs with Constant Congestion.
SIAM Journal on Computing (special issue for STOC 2012), to appear.
A preliminary version appeared in Proc. of the 44th Symposium on Theory of Computing (STOC), pages 855874, 2012.
A video and slides of my talk at the BIRS workshop on approximation algorithms and hardness of approximation, Nov 2011.
 Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan and Yuan Zhou.
Approximation algorithms and hardness of the kroute cut problem.
In Proc. of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages
780799, 2012.
A full version
 Julia Chuzhoy.
An Algorithm for the Graph Crossing Number Problem.
In Proc. of the 43rd annual ACM Symposium on Theory of computing (STOC), pages 303312, 2011.
A full version,
arXiv:1012.0255v1
 Julia Chuzhoy, Yury Makarychev and Anastasios Sidiropoulos.
On Graph Crossing Number and Edge Planarization.
In Proc. of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 10501069, 2011.
A full version.
 MohammadHossein Bateni and Julia Chuzhoy.
Approximation Algorithms for the Directed kTour and kStroll Problems.
Algorithmica 75(3), pages 545561, 2013.
A preliminary version appeared in Proc. of APPROX 2010, Lecture Notes in Computer Science 6302, pages 2538, 2010.
 Parinya Chalermsook and Julia Chuzhoy.
Resource Minimization for Fire Containment.
In Proceedings of the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 13341349, 2010.
 Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
On Allocating Goods to Maximize Fairness.
In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 107116, 2009.
 Julia Chuzhoy and Sanjeev Khanna.
An O(k^3log n)Approximation Algorithm for VertexConnectivity Survivable Network Design.
In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 437441, 2009.
Preliminary version, arXiv:0812.4442, Dec. 2008.
 Julia Chuzhoy and Paolo Codenotti.
Resource Minimization Job Scheduling [Erratum].
In Proceedings of APPROX 2009, Lecture Notes in Computer Science 5687, pages 7083, 2009.
A full version [Erratum].
 Parinya Chalermsook and Julia Chuzhoy.
Maximum Independent Set of Rectangles.
In Proceedings of the Nineteenth Annual ACM SIAM Symposium on Discrete Algorithms (SODA), pages 892901, 2009.
A more detailed version
 Julia Chuzhoy and Sanjeev Khanna.
Algorithms for SingleSource VertexConnectivity.
In Proc. of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 105114, 2008.
Full version containing all proofs
 Tanmoy Chakraborty, Julia Chuzhoy and Sanjeev Khanna.
Network Design for Vertex
Connectivity
In Proc. of the 2008 ACM Symposium on Theory of Computing (STOC), pages 167  176, 2008.
 Julia Chuzhoy and Sanjeev Khanna.
Polynomial FlowCut Gaps and
Hardness of Directed Cut
Problems
Journal of the ACM, Volume 56, issue 2, Article 6, 2009.
Preliminary version appeared
in Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pages 179  188, 2007.
 Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Kunal Talwar.
Hardness of Routing with Congestion in Directed Graphs.
In Proc. of the 39th ACM Symposium on Theory of Computing (STOC),
pages 165178, 2007.
 Julia Chuzhoy and Sanjeev Khanna.
Hardness of Directed Routing with Congestion.
ECCC technical report TR06109, 2006.
 Julia Chuzhoy and Sanjeev Khanna.
Hardness of Cut Problems in Directed Graphs.
In Proc. of the 38th ACM Symposium on Theory of Computing (STOC),
pages 527536, 2006.
Notice: the APXhardness proof for undirected sparsest cut that appears in the Appendix of
this paper is incorrect. A correct proof appears in the Full version of our
multicut paper that appeared at STOC 2007, whose results also subsume the results of this
paper.
 Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
Embedding Ultrametrics Into LowDimensional Spaces.
In Proc. of the 22nd ACM Symposium on Computational Geometry (SOCG),
pages 187196, 2006.
 Chandra Chekuri, Julia Chuzhoy, Liane LewinEytan, Seffi Naor and
Ariel Orda.
Noncooperative multicast and facility location games.
IEEE Journal on Selected Areas in Communication (Special Issue on NonCooperative Behavior in Networking),
vol. 25, no. 6, pp.
11931206, 2007. (Invited paper.)
Preliminary version appeared in
Proc. of the 7th ACM Conference on Electronic Commerce (EC), pages
7281, 2006
 Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna and Lisa Zhang.
Hardness of the Undirected
EdgeDisjoint Paths Problem with Congestion.
In Proc. of the 46th IEEE Symposium on Foundations of Computer Science
(FOCS), pages 226244, 2005.

Julia Chuzhoy and Sanjeev Khanna.
New Hardness Results for Undirected EdgeDisjoint Paths.
Manuscript, 2005.
 Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
LowDistortion
Embeddings of General Metrics into the Line.
In Proc. of the 37th Annual ACM Symposium on Theory of Computing
(STOC), pages 225233, 2005.
Full version
containing all the proofs.
 Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor and Amitabh Sinha.
On the Approximability of Some Network Design Problems.
ACM Transactions on Algorithms (TALG) (special issue of SODA 2005), Volume 4(2), 2008.
Preliminary version appeared in
Proc. of SODA 2005, pages 943951.
 Julia Chuzhoy and Yuval Rabani.
Approximating kmedian with nonuniform capacities.
In Proc. of the 16th Annual ACMSIAM Symposium on Discrete Algorithms
(SODA), pages 952958, 2005.
 Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna and Joseph (Seffi) Naor.
Machine Minimization for Scheduling Jobs with Interval Constraints.
In Proc. of the 45th Annual IEEE Symposium on Foundations of Computer
Science (FOCS) , pages
8190, 2004.
 Julia Chuzhoy and Joseph (Seffi) Naor.
The Hardness of Metric Labeling.
SIAM Journal on Computing, Volume 36
(5), pages 13761386, 2007.
Preliminary version appeared in
Proc. of FOCS 2004, pages
108114.
 Julia Chuzhoy and Joseph (Seffi) Naor.
New hardness results for congestion minimization and machine scheduling.
Journal of the ACM, Volume 53 (50), pages 707721, 2006.
Preliminary version appeared in
Proc. of STOC 2004, pages 2834.
 Julia Chuzhoy, Sudipto Guha, Eran Halperin, Guy Kortsarz, Sanjeev Khanna, Robert Krauthgamer
and Joseph (Seffi) Naor.
Asymmetric kcenter is log*nhard to Approximate.
Journal of the ACM, Volume 52, Issue 4, pages 538551, 2005.
Preliminary version appeared in Proc. of STOC 2004, pages 2127.
 Randeep Bhatia, Julia Chuzhoy, Ari Freund and Joseph (Seffi) Naor.
Algorithmic Aspects of Bandwidth Trading.
In Proc. of the 30th International Colloquium on Automata, Languages, and
Programming (ICALP),
2003.
Lecture Notes in Computer Science 2719, pages. 751766,
SpringerVerlag, 2003.
 Julia Chuzhoy and Joseph (Seffi) Naor.
Covering Problems with Hard Capacities.
SIAM Journal on Computing, Volume 36 (2),
pages 498515, 2006.
Preliminary version appeared in
Proc. of FOCS 2002, pages 481481.

Julia Chuzhoy, Rafail Ostrovsky and Yuval Rabani.
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling
Problems.
Mathematics of Operations Research, Volume 31 (4), pages 730738, 2006.
Preliminary version appeared in
Proc. of FOCS 2001, pages 348356.
 My Master's thesis contains improved algorithms for Metric Labeling when the number of labels is small.
back to my homepage