{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:34:59Z","timestamp":1750307699170,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2008,12,1]],"date-time":"2008-12-01T00:00:00Z","timestamp":1228089600000},"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":[[2008,12]]},"abstract":"<jats:p>\n            Given a set of demands in a directed graph, the\n            <jats:italic>directed congestion minimization<\/jats:italic>\n            problem is to route every demand with the objective of minimizing the heaviest load over all edges. We show that for any constant \u03b5 &gt; 0, there is no \u03a9(log\n            <jats:sup>1\u2212\u03b5<\/jats:sup>\n            <jats:italic>M<\/jats:italic>\n            )-approximation algorithm on networks of size\n            <jats:italic>M<\/jats:italic>\n            unless\n            <jats:italic>NP<\/jats:italic>\n            \u2286\n            <jats:italic>ZPTIME<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              polylog\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ). This bound is almost tight given the\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>M<\/jats:italic>\n            \/log log\n            <jats:italic>M<\/jats:italic>\n            )-approximation via randomized rounding due to Raghavan and Thompson.\n          <\/jats:p>","DOI":"10.1145\/1455248.1455251","type":"journal-article","created":{"date-parts":[[2008,12,17]],"date-time":"2008-12-17T13:25:20Z","timestamp":1229520320000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Almost-tight hardness of directed congestion minimization"],"prefix":"10.1145","volume":"55","author":[{"given":"Matthew","family":"Andrews","sequence":"first","affiliation":[{"name":"Bell Labs, Murray Hill, New Jersey"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bell Labs, Murray Hill, New Jersey"}]}],"member":"320","published-online":{"date-parts":[[2008,12,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"volume-title":"Proceedings of IEEE INFOCOM '05","author":"Andrews M.","key":"e_1_2_1_3_1","unstructured":"Andrews , M. , and Zhang , L . 2005a. Bounds on fiber minimization in optical networks with fixed fiber capacity . In Proceedings of IEEE INFOCOM '05 . IEEE Computer Society Press, Los Alamitos, CA. Andrews, M., and Zhang, L. 2005a. Bounds on fiber minimization in optical networks with fixed fiber capacity. In Proceedings of IEEE INFOCOM '05. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060633"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060632"},{"volume-title":"Proceedings of IEEE INFOCOM '06","author":"Andrews M.","key":"e_1_2_1_6_1","unstructured":"Andrews , M. , and Zhang , L . 2006. Complexity of wavelength assignment in optical network optimization . In Proceedings of IEEE INFOCOM '06 . IEEE Computer Society Press, Los Alamitos, CA. Andrews, M., and Zhang, L. 2006. Complexity of wavelength assignment in optical network optimization. In Proceedings of IEEE INFOCOM '06. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250816"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007364"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Karp R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations R. E. Miller and J. W. Thatcher eds. 85--103.  Karp R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations R. E. Miller and J. W. Thatcher eds. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.1998.649241"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science","volume":"3221","author":"Martens M.","unstructured":"Martens , M. , and Skutella , M . 2004. Flows on few paths: Algorithms and lower bounds . In Proceedings of the 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science , vol. 3221 . Springer-Verlag, New York, 520--531. Martens, M., and Skutella, M. 2004. Flows on few paths: Algorithms and lower bounds. In Proceedings of the 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3221. Springer-Verlag, New York, 520--531."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455251","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1455248.1455251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:00Z","timestamp":1750253400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1455248.1455251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1145\/1455248.1455251"],"URL":"https:\/\/doi.org\/10.1145\/1455248.1455251","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,12]]},"assertion":[{"value":"2006-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}