{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T09:04:26Z","timestamp":1642842266199},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1986,5]]},"abstract":"In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P = NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.<\/jats:p>","DOI":"10.1145\/5925.5933","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"533-550","source":"Crossref","is-referenced-by-count":170,"title":["A unified approach to approximation algorithms for bottleneck problems"],"prefix":"10.1145","volume":"33","author":[{"given":"Dorit S.","family":"Hochbaum","sequence":"first","affiliation":[{"name":"Univ. of California, Berkeley, Berkeley"}]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[{"name":"Univ. of California, Berkeley, Berkeley"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"179","article-title":"The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading","author":"AHO A. V.","year":"1974","journal-title":"Pa."},{"key":"e_1_2_1_2_2","first-page":"290","article-title":"The square of a block is Hamiltonian connected. J. Comb. Theory","volume":"16","author":"CHARTRAND G.","year":"1974","journal-title":"Set. B"},{"key":"e_1_2_1_3_2","volume-title":"Pa.","author":"CHRISTOFIDES N.","year":"1976"},{"key":"e_1_2_1_4_2","first-page":"29","article-title":"The square of every two-connected graph is Hamiltonian. J. Comb. Theory","volume":"16","author":"FLEISCHNER H","year":"1974","journal-title":"Set. B"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0166-218X(83)90102-6","article-title":"An extension of Christofides heuristic to the k-person travelling salesman problem","volume":"6","author":"FRIEZE A.M","year":"1983","journal-title":"Discr. Appl. Math."},{"key":"e_1_2_1_6_2","volume-title":"Freeman","author":"GAREY M. R.","year":"1979"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF01874389","article-title":"When are NP-hard location problems easy?","author":"HOCHBAUM D.S","year":"1984","journal-title":"Ann. Oper. Res."},{"key":"e_1_2_1_9_2","first-page":"189","article-title":"Easy Solutions for the k-Center Problem or the Dominating Set Problem on Random Graphs","volume":"25","author":"HOFHBAUM D.S","year":"1985","journal-title":"Ann. Disc. Math."},{"key":"e_1_2_1_10_2","first-page":"324","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing","author":"HOCHBAUM D. S."},{"key":"e_1_2_1_11_2","unstructured":"HOCHBAUM O. S. NISHIZEKI T. AND SHMOYS D.B. A better than \"best possible\" algorithm to edge color m ultigraphs. J. Algorithms to appear. 10.1016\/0196-6774(86)90039-8 HOCHBAUM O. S. NISHIZEKI T. AND SHMOYS D.B. A better than \"best possible\" algorithm to edge color m ultigraphs. J. Algorithms to appear. 10.1016\/0196-6774(86)90039-8"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","article-title":"Easy and hard bottleneck location problems","volume":"1","author":"NEMHAUSER G.L","year":"1979","journal-title":"Disc. Appl. Math."},{"key":"e_1_2_1_13_2","volume-title":"Que.","author":"LAU H.T.","year":"1980"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322260"},{"key":"e_1_2_1_15_2","unstructured":"NISHIZEKI T. AND SATO M. An approximation algorithm for edge-coloring multigraphs. Preprint. NISHIZEKI T. AND SATO M. An approximation algorithm for edge-coloring multigraphs. Preprint."},{"key":"e_1_2_1_16_2","first-page":"269","article-title":"Guaranteed performance heuristic for the bottleneck travelling salesman problem","volume":"6","author":"PARKER R. G.","year":"1982","journal-title":"Oper. Res. Lett."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/5925.5933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T15:23:16Z","timestamp":1614871396000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,5]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1986,5]]}},"alternative-id":["10.1145\/5925.5933"],"URL":"http:\/\/dx.doi.org\/10.1145\/5925.5933","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1986,5]]}}}