article

New hardness results for congestion minimization and machine scheduling

Authors:

Joseph (Seffi) NaorAuthors Info & Claims

Journal of the ACM (JACM), Volume 53, Issue 5

Pages 707 - 721

https://doi.org/10.1145/1183907.1183908

Published: 01 September 2006 Publication History

Abstract

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is machine scheduling, where we are given a set of jobs, and for each job, there is a list of intervals on 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 overlap in their execution on any machine. Both problems are known to be O(log n/log log n)-approximable via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log n)-hard to approximate unless NP ⊆ DTIME(n^{O(log log log n)}).

References

[1]

Andrews, M., Chuzhoy, J., Khanna, S., and Zhang, L. 2005. Hardness of the undirected edge-disjoint paths problem with congestion. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 226--244.]]

Digital Library

[2]

Andrews, M., and Zhang, L. 2005a. Hardness of the edge-disjoint paths problem with congestion. http://cm.bell-labs.com/cm/ms/who/andrews/edp-congestion.ps.]]

[3]

Andrews, M., and Zhang, L. 2005b. Hardness of the undirected congestion minimization. In Proceedings of the 37th ACM Symposium on Theory of Computing. ACM, New York, 284--293.]]

Digital Library

[4]

Andrews, M., and Zhang, L. 2005c. Hardness of the undirected edge-disjoint paths problem. In Proceedings of the 37th ACM Symposium on Theory of Computing. ACM, New York, 278--283.]]

Digital Library

[5]

Andrews, M., and Zhang, L. 2006. Logarithmic hardness of the directed congestion minimization problem. In Proceedings of the 38th ACM Symposium on Theory of Computing. ACM, New York, 517--526.]]

Digital Library

[6]

Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501--555.]]

Digital Library

[7]

Arora, S., and Safra, S. 1998. Probabilistic checking of proofs: a new characterization of NP. J. ACM 45, 1, 70--122.]]

Digital Library

[8]

Azar, Y., and Regev, O. 2001. Strongly polynomial algorithms for the unsplittable flow problem. In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29.]]

Digital Library

[9]

Bar-Noy, A., Guha, S., Naor, J., and Schieber, B. 2001. Approximating the throughput of multiple machines under real-time scheduling. SIAM J. Comput. 31, 331--352.]]

Digital Library

[10]

Baveja, A., and Srinivasan, A. 2000. Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res. 25, 255--280.]]

Digital Library

[11]

Berman, P., and DasGupta, B. 2000. Multi-phase algorithms for throughput maximization for real-time scheduling. J. Combin. Opt. 4, 3 (Sept.), 307--323.]]

[12]

Chekuri, C., and Khanna, S. 2003. Edge disjoint paths revisited. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 628--637.]]

Digital Library

[13]

Chekuri, C., Khanna, S., and Shepherd, F. B. 2004. Edge disjoint paths in planar graphs. In Proceedings of the 45th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Socitety Press, Los Alamitos, CA, 71--80.]]

Digital Library

[14]

Chekuri, C., Khanna, S., and Shepherd, F. B. 2005. Multicommodity flow, well-linked terminals, and routing problems. In Proceedings of the 37th ACM Symposium on Theory of Computing. ACM, New York, 183--192.]]

Digital Library

[15]

Chekuri, C., Khanna, S., and Shepherd, F. B. 2006a. Edge-disjoint paths in planar graphs with constant congestion. In Proceedings of the 38th ACM Symposium on Theory of Computing. ACM, New York, 757--766.]]

Digital Library

[16]

Chekuri, C., Khanna, S., and Shepherd, F. B. 2006b. An o(&nradic;)-approximation for edp in undirected graphs and directed acyclic graphs. Theory of Computing 2, 137--146.]]

[17]

Chuzhoy, J., Guha, S., Khanna, S., and Naor, J. 2004. Machine minimization for scheduling jobs with interval constraints. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 81--90.]]

Digital Library

[18]

Chuzhoy, J., and Khanna, S. 2005. New hardness results for undirected edge disjoint paths. Manuscript. http://www.cis.upenn.edu/~cisfac/sanjeev/pubs.html/postscript/edpwchardness.ps.gz.]]

[19]

Chuzhoy, J., and Khanna, S. 2006. Hardness of directed routing with congestion. Tech. Rep. TR06-109, Electronic Colloquium on Computational Complexity (ECCC).]]

[20]

Chuzhoy, J., Ostrovsky, R., and Rabani, Y. 2001. Approximation algorithms for the job interval selection problem and related scheduling problems. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 348--356.]]

Digital Library

[21]

Dinur, I., Guruswami, V., and Khot, S. 2002. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k − 3− &epsi;). Tech. Rep. TR02-027, Electronic Colloquium on Computational Complexity (ECCC).]]

[22]

Dinur, I., Guruswami, V., Khot, S., and Regev, O. 2003. A new multilayered PCP and the hardness of hypergraph vertex cover. In Proceedings of the 35th ACM Symposium on Theory of Computing. ACM, New York, 595--601.]]

Digital Library

[23]

Erlebach, T., and Spieksma, F. C. R. 2003. Interval selection: Applications, algorithms, and lower bounds. J. Algorithms 46, 1, 27--53.]]

Digital Library

[24]

Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.]]

Digital Library

[25]

Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., and Yannakakis, M. 2003. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67, 3, 473--496.]]

Digital Library

[26]

Kleinberg, J. M. 1996. Approximation algorithms for disjoint paths problems. Ph.D. dissertation. MIT, Cambridge, MA.]]

Digital Library

[27]

Kolliopoulos, S. G., and Stein, C. 1998. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization. ACM, New York, 153--168.]]

[28]

Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., and Shmoys, D. B. 1993. Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science, vol. 4: Logistics for Production and Inventory. North Holland, Amsterdam, The Netherlands, 445--522.]]

[29]

Raghavan, P., and Thompson, C. D. 1987. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365--374.]]

Digital Library

[30]

Raz, R. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3, 763--803.]]

Digital Library

[31]

Srinivasan, A. 1997. Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 416--425.]]

Digital Library

[32]

Varadarajan, K., and Venkataraman, G. 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 379--380.]]

Digital Library

Cited By

Hyatt-Denesik DRahgoshay MSalavatipour M(2024)Approximations for Throughput MaximizationAlgorithmica10.1007/s00453-023-01201-486:5(1545-1577)Online publication date: 9-Jan-2024
https://doi.org/10.1007/s00453-023-01201-4
Zhang XGu WZhang HWang M(2019)Hybrid Communication Path Orchestration for 5G Heterogeneous Ultra-Dense NetworksIEEE Network10.1109/MNET.2019.180040233:4(112-118)Online publication date: Jul-2019
https://doi.org/10.1109/MNET.2019.1800402
Li YZhang JChen XLi JDing J(2017)An accurate resource scheduling system for virtual machines based on CPU load monitoring and assessmentCluster Computing10.1007/s10586-017-1344-z21:2(1395-1410)Online publication date: 13-Nov-2017
https://doi.org/10.1007/s10586-017-1344-z
Show More Cited By

Index Terms

New hardness results for congestion minimization and machine scheduling
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Hardness of routing with congestion in directed graphs
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem ...
New hardness results for congestion minimization and machine scheduling
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

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 ...
Hardness of Precedence Constrained Scheduling on Identical Machines

In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 53, Issue 5

September 2006

173 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1183907

Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2006

Published in JACM Volume 53, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
894
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hyatt-Denesik DRahgoshay MSalavatipour M(2024)Approximations for Throughput MaximizationAlgorithmica10.1007/s00453-023-01201-486:5(1545-1577)Online publication date: 9-Jan-2024
https://doi.org/10.1007/s00453-023-01201-4
Zhang XGu WZhang HWang M(2019)Hybrid Communication Path Orchestration for 5G Heterogeneous Ultra-Dense NetworksIEEE Network10.1109/MNET.2019.180040233:4(112-118)Online publication date: Jul-2019
https://doi.org/10.1109/MNET.2019.1800402
Li YZhang JChen XLi JDing J(2017)An accurate resource scheduling system for virtual machines based on CPU load monitoring and assessmentCluster Computing10.1007/s10586-017-1344-z21:2(1395-1410)Online publication date: 13-Nov-2017
https://doi.org/10.1007/s10586-017-1344-z
Im SShadloo MScheideler CGilbert S(2016)Brief AnnouncementProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935824(207-209)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935824
Jiaqi Zheng Hong Xu Xiaojun Zhu Guihai Chen Yanhui Geng (2016)We've got you covered: Failure recovery with backup tunnels in traffic engineering2016 IEEE 24th International Conference on Network Protocols (ICNP)10.1109/ICNP.2016.7784449(1-10)Online publication date: Nov-2016
https://doi.org/10.1109/ICNP.2016.7784449
Zhang JChen XLi JLi X(2012)Task mapper and application-aware virtual machine scheduler oriented for parallel computingJournal of Zhejiang University SCIENCE C10.1631/jzus.C110021713:3(155-177)Online publication date: 6-Mar-2012
https://doi.org/10.1631/jzus.C1100217
Chalermsook PChuzhoy JEne ALi SKarloff HPitassi T(2012)Approximation algorithms and hardness of integral concurrent flowProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214040(689-708)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214040
Lee STurner JDaskin MHomem-de-Mello TSmilowitz K(2012)Improving fleet utilization for carriers by interval schedulingEuropean Journal of Operational Research10.1016/j.ejor.2011.10.019218:1(261-269)Online publication date: Apr-2012
https://doi.org/10.1016/j.ejor.2011.10.019
Kao MChen JRutter IWagner D(2012)Competitive Design and Analysis for Machine-Minimizing Job Scheduling ProblemAlgorithms and Computation10.1007/978-3-642-35261-4_11(75-84)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35261-4_11
Khuller SLi JSaha BCharikar M(2010)Energy efficient scheduling via partial shutdownProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873711(1360-1372)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873711
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents