Julia Chuzhoy's Publications
Julia Chuzhoy's publications
Julia Chuzhoy, David H.K. Kim and Shi Li.
Improved Approximation for Node-Disjoint Paths in Planar Graphs.
STOC 2016, to appear.
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 645-654, 2015. For a full version, see this paper.
Julia Chuzhoy and David H.K. Kim.
On Approximating Node-Disjoint Paths in Grids . In Proc. of APPROX 2015, LIPIcs-Leibniz International Proceedings in Informatics (Vol. 40).
Chandra Chekuri and Julia Chuzhoy.
Degree-3 Treewdith Sparsifiers .
In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) , pages 242-255, 2015.
A full version , arxiv:1410.1016
Julia Chuzhoy.
Improved Bounds for the Flat Wall Theorem .
In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) , pages 256-275, 2015.
A full version , arxiv:1410.9276
Chandra Chekuri and Julia Chuzhoy.
Polynomial Bounds for the Grid-Minor Theorem .
In Proc. of the 46th Annual Symposium on the Theory of Computing (STOC) , pages 60-69, 2014.
A full version , arxiv:1305.6577
Chandra Chekuri and Julia Chuzhoy.
Large-Treewidth Graph Decompositions and Applications .
In Proc. of the 45th Annual ACM Symposium on Theory of Computing (STOC) ,
pages 291-300, 2013.
A full version , arXiv:1304.1577 .
Julia Chuzhoy and Shi Li.
A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2 .
In Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 233-242, 2012. A co-winner 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 73-84, 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 689-708, 2012.
A full version
Julia Chuzhoy.
On Vertex Sparsifiers with Steiner Nodes .
In Proc. of the 44th Symposium on Theory of Computing (STOC) , pages 673-688, 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 855-874, 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 k-route cut problem.
In Proc. of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages
780-799, 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 303-312, 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 Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1050-1069, 2011.
A full version .
MohammadHossein Bateni and Julia Chuzhoy.
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems .
Algorithmica 75(3), pages 545-561, 2013.
A preliminary version appeared in Proc. of APPROX 2010 , Lecture Notes in Computer Science 6302, pages 25-38, 2010.
Parinya Chalermsook and Julia Chuzhoy.
Resource Minimization for Fire Containment .
In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1334-1349, 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 107-116, 2009.
Julia Chuzhoy and Sanjeev Khanna.
An O(k^3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 437-441, 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 70-83, 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 892-901, 2009. A more detailed version
Julia Chuzhoy and Sanjeev Khanna.
Algorithms for Single-Source Vertex-Connectivity .
In Proc. of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 105-114, 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 Flow-Cut 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 165-178, 2007.
Julia Chuzhoy and Sanjeev Khanna.
Hardness of Directed Routing with Congestion.
ECCC technical report TR06-109, 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 527-536, 2006.
Notice: the APX-hardness 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 Low-Dimensional Spaces.
In Proc. of the 22nd ACM Symposium on Computational Geometry (SOCG) ,
pages 187-196, 2006.
Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Seffi Naor and
Ariel Orda.
Non-cooperative multicast and facility location games.
IEEE Journal on Selected Areas in Communication (Special Issue on Non-Cooperative Behavior in Networking),
vol. 25, no. 6, pp.
1193-1206, 2007. (Invited paper.)
Preliminary version appeared in
Proc. of the 7th ACM Conference on Electronic Commerce (EC) , pages
72-81, 2006
Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna and Lisa Zhang.
Hardness of the Undirected
Edge-Disjoint Paths Problem with Congestion .
In Proc. of the 46th IEEE Symposium on Foundations of Computer Science
(FOCS) , pages 226-244, 2005.
Julia Chuzhoy and Sanjeev Khanna.
New Hardness Results for Undirected Edge-Disjoint Paths.
Manuscript, 2005.
Mihai Badoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos.
Low-Distortion
Embeddings of General Metrics into the Line .
In Proc. of the 37th Annual ACM Symposium on Theory of Computing
(STOC) , pages 225-233, 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 943-951.
Julia Chuzhoy and Yuval Rabani.
Approximating k-median with non-uniform capacities.
In Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA) , pages 952-958, 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
81-90, 2004.
Julia Chuzhoy and Joseph (Seffi) Naor.
The Hardness of Metric Labeling . SIAM Journal on Computing , Volume 36
(5), pages 1376-1386, 2007.
Preliminary version appeared in
Proc. of FOCS 2004, pages
108-114.
Julia Chuzhoy and Joseph (Seffi) Naor.
New hardness results for congestion minimization and machine scheduling.
Journal of the ACM , Volume 53 (50), pages 707-721, 2006.
Preliminary version appeared in
Proc. of STOC 2004, pages 28-34.
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Guy Kortsarz, Sanjeev Khanna, Robert Krauthgamer
and Joseph (Seffi) Naor.
Asymmetric k-center is log*n-hard to Approximate.
Journal of the ACM , Volume 52, Issue 4, pages 538-551, 2005.
Preliminary version appeared in Proc. of STOC 2004, pages 21-27.
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. 751-766,
Springer-Verlag, 2003.
Julia Chuzhoy and Joseph (Seffi) Naor.
Covering Problems with Hard Capacities.
SIAM Journal on Computing , Volume 36 (2),
pages 498-515, 2006.
Preliminary version appeared in
Proc. of FOCS 2002, pages 481-481.
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 730-738, 2006.
Preliminary version appeared in
Proc. of FOCS 2001, pages 348-356.
My Master's thesis contains improved algorithms for Metric Labeling when the number of labels is small.
back to my homepage