{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T04:15:35Z","timestamp":1792556135374,"version":"4.5.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>\n            We study the approximability of two natural NP-hard problems. The first problem is\n            <jats:italic>congestion minimization<\/jats:italic>\n            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\n            <jats:italic>machine scheduling<\/jats:italic>\n            , 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\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            \/log log\n            <jats:italic>n<\/jats:italic>\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 \u2126(log log\n            <jats:italic>n<\/jats:italic>\n            )-hard to approximate unless NP \u2286 DTIME(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (log log log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1183907.1183908","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"707-721","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["New hardness results for congestion minimization and machine scheduling"],"prefix":"10.1145","volume":"53","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"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.]]  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.]]","DOI":"10.1145\/1060590.1060632"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060633"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060632"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132592"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29","author":"Azar Y."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"key":"e_1_2_1_11_1","first-page":"3","article-title":"Multi-phase algorithms for throughput maximization for real-time scheduling","volume":"4","author":"Berman P.","year":"2000","journal-title":"J. Combin. Opt."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Chekuri C."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.27"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060618"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132621"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.38"},{"key":"e_1_2_1_18_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_19_1","volume-title":"Tech. Rep. TR06-109, Electronic Colloquium on Computational Complexity (ECCC).]]","author":"Chuzhoy J.","year":"2006"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Chuzhoy J."},{"key":"e_1_2_1_21_1","volume-title":"Tech. Rep. TR02-027, Electronic Colloquium on Computational Complexity (ECCC).]]","author":"Dinur I.","year":"2002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780629"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00291-2"},{"key":"e_1_2_1_24_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.]]   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_26_1","unstructured":"Kleinberg J. M. 1996. Approximation algorithms for disjoint paths problems. Ph.D. dissertation. MIT Cambridge MA.]]   Kleinberg J. M. 1996. Approximation algorithms for disjoint paths problems. Ph.D. dissertation. MIT Cambridge MA.]]"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization. ACM","author":"Kolliopoulos S. G."},{"key":"e_1_2_1_28_1","volume-title":"Logistics for Production and Inventory. North Holland","author":"Lawler E. L.","year":"1993"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796366"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Varadarajan K."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1183907.1183908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1183907.1183908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:35Z","timestamp":1750259195000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1183907.1183908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1183907.1183908"],"URL":"https:\/\/doi.org\/10.1145\/1183907.1183908","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}