Papers

• Approximation
• Constraint Satisfaction Problems / Structure in Approximation Classes
• Databases
• Network Design and Routing
• Scheduling
• Miscellaneous

Approximation

• Algorithms for Single-Source Vertex-Connectivity.
  (with J. Chuzhoy).
  Submitted, 2008.

This paper improves the main result of the STOC'08 paper, by showing an O(klog n)-approximation
algorithm for the single-source k-vertex connectivity problem. We also give a poly(k log n)-approximation
for the vertex cost variation of the same problem.


• 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 Directed Routing with Congestion.
  (with J. Chuzhoy).
  ECCC Report, 2006.
  
  
• 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.



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



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



• Algorithms for Minimizing Weighted Flow Time.
  (with C. Chekuri and A. Zhu)
  Proc. 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.



• Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation.
  (with C. Chekuri, S. Naor, and L. Zosin)
  Proc. 12th Annual Symposium on Discrete Algorithms (SODA), pp. 109-118, 2001.
  Full version to appear in SIAM Journal on Discrete Mathematics (SIDMA).



• A Deterministic Algorithm for the Cost-Distance Problem.
  (with C. Chekuri and S. Naor) Proc. 12th Annual Symposium on Discrete Algorithms (SODA), pp. 232-233, 2001 (short form).



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



• Directed Network Design Problems with Orientation Constraints.
  (with J. Naor and F.B. Shepherd)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), pp. 663-671, 2000.
  Full version to appear in SIAM Journal on Discrete Mathematics (SIDMA).



• 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), pp. 223-232, 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.
  Full version appears in SIAM Journal on Discrete Mathematics (SIDMA), 18(1), 30-40, 2004.



• 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), pp. 32-44, 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), pp. 1-12, 1999.
  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)
  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.
  Full version will appear in SIAM Journal on Computing (SICOMP).



• 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.
  Full version appears in special issue of Journal of Computer and System Sciences (JCSS), devoted to STOC 98 papers.



• 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.
  Bell Labs Technical Journal, Spring Issue, pp. 36-41, 1997.
  Also appeared in 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.
  Full version will appear in SIAM Journal on Computing (SICOMP).



• 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), 1996, pp.
  61-67. Full version appears in Chicago Journal of Theoretical Computer Science (CJTCS), 1997.



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



• Approximation Algorithms for the Largest Common Subtree Problem.
  (with R. Motwani and F.F. Yao)
  Stanford University Tech. Report STAN-CS-TR-95-1545 , 1995.
  



• 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.
  Full version appears in SIAM Journal on Computing (SICOMP), Vol. 28, No. 1, pp. 164-191, 1999.



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

Constraint Satisfaction Problems / Structure in Approximation Classes

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



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



• The Optimization Complexity of Constraint Satisfaction Problems.
  (with M. Sudan)
  Technical Report TR96-028, Electronic Colloquium on Computational Complexity (ECCC), 1996.



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



• 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.
  SIAM Journal on Computing (SICOMP), Vol. 28, No. 1, Feb. 1999, pp. 164-191.
  (Cross-listed under "Approximation Algorithms")

Databases

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



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



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



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



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



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

Network Design and Routing

• Hardness of Directed Routing with Congestion.
  (with J. Chuzhoy).
  ECCC Report, 2006.
  
  
• 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.



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



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



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



• A Deterministic Algorithm for the Cost-Distance Problem.
  (with C. Chekuri and S. Naor) Proc. 12th Annual Symposium on Discrete Algorithms (SODA), 2001 (short form).
  ( Cross-listed under "Approximation Algorithms")
  
  
• Directed Network Design Problems with Orientation Constraints.
  (with J. Naor and F.B. Shepherd)
  Proc. 11th Annual Symposium on Discrete Algorithms (SODA), 2000.
  ( Cross-listed under "Approximation Algorithms")



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

( Cross-listed under "Approximation Algorithms")


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

( Cross-listed under "Approximation Algorithms")


• 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.
  ( Cross-listed under "Approximation Algorithms")



• 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.
  ( Cross-listed under "Approximation Algorithms")



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



• A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem.
  Bell Labs Technical Journal, Spring 1997, pp. 36-41.
  ( Cross-listed under "Approximation Algorithms")

Scheduling

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



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



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

(Cross-listed under "Approximation Algorithms")


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

(Cross-listed under "Approximation Algorithms")


• 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), pp. 32-44, 1999.

(Cross-listed under "Approximation Algorithms")


• 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), pp. 1-12, 1999.
  
  (Cross-listed under "Approximation Algorithms")


• 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.
  ( Cross-listed under "Approximation Algorithms")



• On Indexed Data Broadcast.
  (with S. Zhou)
  Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 463-472, 1998.
  Full version appears in special issue of Journal of Computer and System Sciences (JCSS), devoted to STOC 98 papers.
  ( Cross-listed under "Approximation Algorithms")

Miscellaneous

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



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



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



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


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



• On Certificates and Lookahead in Dynamic Graph Problems.
  (with R. Motwani and R. Wilson)
  Proc. 7th Annual Symposium on Discrete Algorithms (SODA), 1996, pp. 222-231.
  Full version appears in Algorithmica (1998) Vol. 21, pp. 377-394.



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



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