New hardness results for congestion minimization and machine scheduling

ABSTRACT

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. We are given a directed capacitated graph and a set of source-sink pairs. The goal is to route all pairs with minimum congestion on the network edges. A special well-studied case of this problem is the edge-disjoint paths problem, where all edges have unit capacities. The second problem is discrete machine scheduling, where we are given a set of jobs, and for each job a list of intervals in which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled, such that no two jobs assigned to the same machine overlap. Both problems are known to be O(log n/log log n)-approximable via the randomized rounding technique of Raghavan and Thompson. However, until recently, only a Max SNP hardness was known for each problem. We make some progress in closing this gap by showing that both problem are Ω(log log n)-hard to approximate unless NP ⊆ DTIME(n^{O(log log log n)}). Our hardness proof for congestion minimization holds even for the special case of the edge-disjoint paths problem.

REFERENCES

• 1: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 2: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 3: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 4: Amotz Bar-Noy , Sudipto Guha, Approximating the Throughput of Multiple Machines in Real-Time Scheduling, SIAM Journal on Computing, v.31 n.2, p.331-352, 2001 [doi>10.1137/S0097539799354138]
• 5: P. Berman and B. DasGupta. Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3):307--323, 2000.
• 6: Chandra Chekuri , Sanjeev Khanna, Edge disjoint paths revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: J. Chuzhoy, S. Guha, S. Khanna, and J. Naor. Approximation algorithms for machine scheduling. Manuscript, 2003.
• 8: J. Chuzhoy, Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.348, October 14-17, 2001
• 9: I. Dinur, V. Guruswami, and S. Khot. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-ε). ECCC Report TR02-027, Electronic Colloquium on Computational Complexity, 2002.
• 10: Irit Dinur , Venkatesan Guruswami , Subhash Khot , Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780629]
• 11: Thomas Erlebach , Frits C. R. Spieksma, Interval selection: applications, algorithms, and lower bounds, Journal of Algorithms, v.46 n.1, p.27-53, January 2003 [doi>10.1016/S0196-6774(02)00291-2]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.19-28, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301262]
• 14: Eran Halperin , Robert Krauthgamer, Polylogarithmic inapproximability, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780628]
• 15: Sanjeev Khanna , Madhu Sudan , Luca Trevisan , David P. Williamson, The Approximability of Constraint Satisfaction Problems, SIAM Journal on Computing, v.30 n.6, p.1863-1920, 2001 [doi>10.1137/S0097539799349948]
• 16: Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997
• 17: Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
• 18: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science, Vol. 4: Logistics for Production and Inventory, pages 445--522, North Holland, 1993.
• 19: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 20: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, congestion minimization, hardness of approximation, machine scheduling, routing