Books and Surveys

Conference Papers

• Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs.
  (with A. Goel and M. Kapralov).
  To appear in SODA , 2009.


• The Ratio Index for Budgeted Learning, with Applications.
  (with A. Goel and B. Null).
  To appear in SODA , 2009.


• Algorithms for Single-Source Vertex-Connectivity.
  (with J. Chuzhoy).
  To appear in FOCS , 2008.


• Algorithms for 2-Route Cut Problems.
  (with Chandra Chekuri)
  Proc. 35th International Colloquium on Automata, Languages, and Programming (ICALP), 2008.


• Network Design for Vertex Connectivity.
  (with T. Chakraborty and J. Chuzhoy).
  40th ACM Symposium on Theory of Computing (STOC), 2008.


• Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems.
  (with J. Chuzhoy).
  39th ACM Symposium on Theory of Computing (STOC), 2007.

Full version of the paper is here.


• Hardness of Routing with Congestion in Directed Graphs.
  (with J. Chuzhoy, V. Guruswami, and K. Talwar).
  39th ACM Symposium on Theory of Computing (STOC), 2007.



• Hardness of Cut Problems in Directed Graphs.
  (with J. Chuzhoy).
  38th ACM Symposium on Theory of Computing (STOC), 2006.



• Edge-Disjoint Paths in Planar Graphs with Constant Congestion.
  (with C. Chekuri and F. B. Shepherd).
  38th ACM Symposium on Theory of Computing (STOC), 2006.



• Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data.
  (with M. B. Greenwald, K. Kunal, B. C. Pierce, and A. Schmitt)
  21st International Symposium on DIStributed Computing (DISC), 2006, pp. 269--28.



• On the Complexity of Graph Self-Assembly in Accretive Systems.
  (with S. Angelov and M. Visontai)
  12th International Meeting on DNA Computing (DNA), 2006, pp. 95--110.



• Efficient Enumeration of Phylogenetically Informative Strings.
  (with S. Angelov, B. Harb, S. Kannan, and J. Kim)
  10th Conference on Research in Computational Biology (RECOMB), 2006.



• Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
  (with M. Andrews, J. Chuzhoy, and L. Zhang).
  Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005.



• New Hardness Results for Undirected Edge-Disjoint Paths.
  (with J. Chuzhoy).
  Manuscript, 2005.



• Multicommodity flow, well-linked terminals, and routing problems.
  (with C. Chekuri and F. B. Shepherd).
  37th ACM Symposium on Theory of Computing (STOC), 2005.



• Edge Disjoint Paths in Planar Graphs.
  (with C. Chekuri and F. B. Shepherd).
  Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), 2004.



• Machine Minimization for Scheduling Jobs with Interval Constraints.
  (with J. Chuzhoy, S. Guha, and S. Naor).
  Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), 2004.



• Asymmetric k-center is log^*n-hard to Approximate.
  (with J. Chuzhoy, S. Guha, E. Halperin, G. Kortsarz, R. Krauthgamer, and S. Naor).
  36th ACM Symposium on Theory of Computing (STOC), 2004.



• The All-or-Nothing Multicommodity Flow Problem.
  (with C. Chekuri and F. B. Shepherd).
  36th ACM Symposium on Theory of Computing (STOC), 2004.



• Multi-processor Scheduling to Minimize Flowtime with eps Resource Augmentation.
  (with C. Chekuri, A. Goel, and A. Kumar).
  36th ACM Symposium on Theory of Computing (STOC), 2004.



• Approximating Longest Directed Paths and Cycles.
  (with Andreas Björklund and Thore Husfeldt)
  Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP), 2004.



• Power-Conserving Computation of Order-Statistics over Sensor Networks.
  (with M. Greenwald).
  23rd ACM Symposium on Principles of Database Systems (PODS), 275-285, 2004.



• Randomized pursuit-evasion with limited visibility.
  (with V. Isler and S. Kannan).
  Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp. 1060-1069, 2004.



• Reconstructing strings from random traces.
  (with T. Batu, S. Kannan, and A. McGregor).
  Proc. 15th Annual Symposium on Discrete Algorithms (SODA), pp. 910-918, 2004.



• Edge Disjoint Paths Revisited.
  (with C. Chekuri).
  Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003.



• Selection with Monotone Comparison Costs.
  (with S. Kannan)
  Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003.



• Approximation Schemes for Preemptive Weighted Flow Time.
  (with C. Chekuri).
  34th ACM Symposium on Theory of Computing (STOC), 2002.



• On Propagation of Deletions and Annotations through Views.
  (with P. Buneman and W. Tan).
  21st ACM Symposium on Principles of Database Systems (PODS), 2002.



• Archiving Scientific Data.
  (with P. Buneman, K. Tajima, and W. Tan.)
  ACM SIGMOD International Conference on Management of Data (SIGMOD), 2002.



• Algorithms for Minimizing Weighted Flow Time.
  (with C. Chekuri and A. Zhu)
  33rd ACM Symposium on Theory of Computing (STOC), pp. 84--93, 2001.



• A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.
  (with C. Chekuri)
  28th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 848--861, 2001.



• Fair Real-time Traffic Scheduling Over a Wireless LAN.
  (with M. Adamou, I. Lee, I. Shin, and S. Zhou)
  22nd IEEE Real-Time Systems Symposium (RTSS), 2001.



• On Computing Functions with Uncertainity.
  (with W. Tan)
  20th ACM Symposium on Principles of Database Systems (PODS), 2001.



• Space-Efficient Online Computation of Online Summaries.
  (with M. Greenwald)
  ACM SIGMOD International Conference on Management of Data (SIGMOD), 2001.



• Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation.
  (with C. Chekuri, S. Naor, and L. Zosin)
  12th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001.



• A Deterministic Algorithm for the Cost-Distance Problem.
  (with C. Chekuri and S. Naor),
  12th ACM-SIAM Symposium on Discrete Algorithms (SODA), (short paper) 2001.



• Why and Where: A Characterization of Data Provenance.
  (with P. Buneman and W. Tan)
  8th International Conference on Database Theory (ICDT), pp. 316--330, 2000.



• Data Provenance: Some Basic Issues.
  (with P. Buneman and W. Tan)
  8th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 87--93, 2000.



• On the Hardness of $4$-coloring a $3$-colorable Graph.
  (with V. Guruswami)
  Proc. 15th IEEE Computational Complexity Conference (CCC), pp. 188-197, 2000.



• Watermarking Maps: Hiding Information in Structured Data.
  (with F. Zane)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.



• A PTAS for the Multiple Knapsack Problem.
  (with C. Chekuri)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.



• Directed Network Design Problems with Orientation Constraints.
  (with J. Naor and F.B. Shepherd)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.



• Approximation Algorithms for Data Placement on Parallel Disks.
  (with L. Golubchik, S. Khuller, R. Thurimella and A. Zhu)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.



• Approximation Schemes for Scheduling to Minimize Average Completion Time with Release Dates.
  (with F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, I. Milis, M. Queyranne, M. Skutella, C. Stein and M. Sviridenko)
  Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999.



• Space-Time Tradeoffs for Graph Properties.
  (with Y. Dodis)
  Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP), 1999.
  


• Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.
  (with M. Adler, R. Rajaraman and A. Rosen)
  Proc. 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1999.
  


• Near-Optimal Hardness Results and Approximation Algorithms for
  Edge-Disjoint Paths and Related Problems.
  (with V. Guruswami, B. Shepherd, R. Rajaraman and M. Yannakakis)
  Proc. 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 19-28, 1999.



• Designing Networks with Bounded Pairwise Distance.
  (with Y. Dodis)
  Proc. 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750-759, 1999.



• On Multidimensional Packing Problems.
  (with C. Chekuri)
  Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 185-194, 1999.



• Page Replacement for General Caching Problems.
  (with S. Albers and S. Arora)
  Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 31-40, 1999.



• The 2-Catalog Segmentation Problem
  (with Y. Dodis and V. Guruswami)
  Proc. 10th Annual Symposium on Discrete Algorithms (SODA), pp. 897-898, 1999 (Short Form).



• Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch.
  (with M. Andrews and K. Kumaran)
  Proc. 18th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 1999.



• On Indexed Data Broadcast.
  (with S. Zhou)
  Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 463-472, 1998.



• On Broadcast Disk Paging.
  (with V. Liberatore)
  Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 634-643, 1998.



• On Wireless Spectrum Estimation and Generalized Graph Coloring.
  (with K. Kumaran)
  Proc. 17th Joint Conf. of IEEE Computer and Communications Societies (INFOCOM), 1998.



• On Approximating Rectangle Tiling and Packing.
  (with S. Muthukrishnan and M. Paterson)
  Proc. 9th Annual Symposium on Discrete Algorithms (SODA), pp. 384-393, 1998.



• A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem.
  INFORMS 98.



• Efficient Array Partitioning.
  (with S. Muthukrishnan and S. Skiena)
  Proc. 24th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 616-626, 1997.



• Angular-Metric TSP.
  (with A. Aggarwal, D. Coppersmith, R. Motwani and B. Schieber)
  Proc. 8th Annual Symposium on Discrete Algorithms (SODA), pp. 221-229, 1997.



• Constraint Satisfaction: The Approximability of Minimization Problems.
  (with M. Sudan and L. Trevisan)
  Proc. 12th Annual IEEE Computational Complexity Conference (CCC), pp. 282-296, 1997.



• A Complete Classification of the Approximability of Maximization
  Problems Derived from Boolean Constraint Satisfaction.
  (with M. Sudan and D.P. Williamson)
  Proc. 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 11-20, 1997.



• Towards a Syntactic Characterization of PTAS.
  (with R. Motwani)
  Proc. 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 329-337, 1996.



• On Certificates and Lookahead in Dynamic Graph Problems.
  (with R. Motwani and R. Wilson)
  Proc. 7th Annual Symposium on Discrete Algorithms (SODA), pp. 222-231, 1996.



• On the Hardness of Max $k$-Cut and its Dual.
  (with V. Kann, J. Lagergren and A. Panconesi)
  Proc. 5th Israel Symposium on Theory and Computing Systems (ISTCS), pp. 61-67, 1996.



• On Syntactic versus Computational Views of Approximability.
  (with R. Motwani, M. Sudan and U. Vazirani)
  Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 819-830, 1994.



• On the Hardness of Approximating the Chromatic Number.
  (with N. Linial and S. Safra)
  Proc. 2nd Israel Symposium on Theory and Computing Systems (ISTCS),
  pp. 250-260, 1993.

Journal Papers

• A PTAS for the Multiple Knapsack Problem.
  (with C. Chekuri)
  SIAM Journal on Computing (SICOMP), 35(3), 713-728, 2005.



• Directed Network Design Problems with Orientation Constraints.
  (with J. Naor and F.B. Shepherd)
  SIAM Journal on Discrete Mathematics (SIDMA), 19(1), 245-257, 2005.



• Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation.
  (with C. Chekuri, S. Naor, and L. Zosin)
  SIAM Journal on Discrete Mathematics (SIDMA), 18(3), 608-625, 2004.



• On the Hardness of $4$-coloring a $3$-colorable Graph.
  (with V. Guruswami)
  SIAM Journal on Discrete Mathematics (SIDMA), 18(1), 30-40, 2004.



• On Multidimensional Packing Problems.
  (with C. Chekuri)
  SIAM Journal on Computing (SICOMP), 33(4), 837-851, 2004.



• Archiving Scientific Data.
  (with P. Buneman, K. Tajima, and W. Tan.)
  ACM Transactions on Database Systems (TODS), 29: 2-42, 2004. (Special issue devoted to papers invited from SIGMOD/PODS 2003.)



• Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.
  (with M. Adler, S. Khanna, R. Rajaraman, A. Rosén)
  Algorithmica 36(2): 123-152, 2003.
  
  
• Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
  (with V. Guruswami, B. Shepherd, R. Rajaraman and M. Yannakakis)
  Journal of Computer and System Sciences (JCSS), 67(3), 473-496, 2003.



• The Approximability of Constraint Satisfaction Problems.
  (with M. Sudan, L. Trevisan, and D.P. Williamson)
  SIAM Journal on Computing (SICOMP), Vol. 30, No. 6, pp. 1863-1920, 2000.



• On the Hardness of Approximating the Chromatic Number.
  (with N. Linial and S. Safra)
  Combinatorica , Vol. 20, No. 3, pp. 393--415, 2000.



• On Indexed Data Broadcast.
  (with S. Zhou)
  Special issue of Journal of Computer and System Sciences (JCSS), devoted to papers invited from STOC 98, No. 60, pp. 575-591, 2000.



• On Broadcast Disk Paging.
  (with V. Liberatore)
  SIAM Journal on Computing (SICOMP), Vol. 29, No. 5, 1683-1702, 2000.
  
  
• Angular-Metric TSP.
  (with A. Aggarwal, D. Coppersmith, R. Motwani and B. Schieber)
  SIAM Journal on Computing (SICOMP), Vol. 29, No. 3, pp. 697-711, 1999.



• On Syntactic versus Computational Views of Approximability.
  (with R. Motwani, M. Sudan and U. Vazirani)
  SIAM Journal on Computing (SICOMP), Vol. 28, No. 1, pp. 164-191, 1999.



• On Certificates and Lookahead in Dynamic Graph Problems.
  (with R. Motwani and R. Wilson)
  Algorithmica Vol. 21, pp. 377-394, 1998.



• A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem.
  Bell Labs Technical Journal, Spring Issue, pp. 36-41, 1997.



• On the Hardness of Max $k$-Cut and its Dual.
  (with V. Kann, J. Lagergren and A. Panconesi)
  Chicago Journal of Theoretical Computer Science (CJTCS), 1997.



• A Linear Time Sequential Diagnosis Algorithm for Hypercubes.
  (with W. K. Fuchs)
  Journal of Parallel and Distributed Computing (JPDC), April, pp. 48-53, 1995.



• A Graph Partitioning Approach to Sequential Diagnosis.
  (with W. K. Fuchs)
  IEEE Transactions on Computers (IEEETC), January, pp. 39-47, 1997.