Julia Chuzhoy's Publications

• Chandra Chekuri and Julia Chuzhoy.
  Large-Treewidth Graph Decompositions and Applications.
  STOC 2013, to appear.
  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.
  In Proc. of the 44th Symposium on Theory of Computing (STOC), pages 855-874, 2012.
  Invited to the SICOMP STOC 2012 Special Issue.
  
  • A full version.
    
  • A preliminary version: arXiv:1107.2554v1, 2011.
    
  • 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.
  • Full version.
  • Preliminary version, arXiv:0901.0205v1, Jan. 2009.
  • "Detailed" slides
  
  
  
• 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.
  In Proceedings of APPROX 2009, Lecture Notes in Computer Science 5687, pages 70-83, 2009.
  A full version.
  
  
• 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