{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:08:04Z","timestamp":1750478884401,"version":"3.41.0"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, <jats:italic>in practice<\/jats:italic>, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.<\/jats:p>\n\t  <jats:p>We analyse the performance of three related approximation algorithms for the uncapacitated facility location problem (from Jain, Mahdian, Markakis, Saberi and Vazirani (2003) and Mahdian, Ye and Zhang (2002)) when each is applied to an instances created by placing <jats:italic>n<\/jats:italic> points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.<\/jats:p>","DOI":"10.1017\/s096354830600798x","type":"journal-article","created":{"date-parts":[[2006,8,29]],"date-time":"2006-08-29T14:00:03Z","timestamp":1156860003000},"page":"713-732","source":"Crossref","is-referenced-by-count":2,"title":["On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem"],"prefix":"10.1017","volume":"16","author":[{"given":"ABRAHAM D.","family":"FLAXMAN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALAN M.","family":"FRIEZE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUAN CARLOS","family":"VERA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,9,1]]},"reference":[{"key":"S096354830600798X_manual_ref-16","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"S096354830600798X_manual_ref-8","first-page":"119","volume-title":"Discrete Location Theory","author":"Cornu\u00e9jols","year":"1990"},{"key":"S096354830600798X_manual_ref-13","unstructured":"[13] Korupolu, M. R. , Plaxton, C. G. and Rajaraman, R. (1998) Analysis of a local search heuristic for facility location problems. In Proc. 9th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 1\u201310."},{"key":"S096354830600798X_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90181-9"},{"key":"S096354830600798X_manual_ref-3","doi-asserted-by":"crossref","unstructured":"[3] Barahona, F. and Chudak, F. A. (1999) Solving large scale uncapacitated facility location problems. In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic, pp. 48\u201362.","DOI":"10.1007\/978-1-4757-3145-3_4"},{"key":"S096354830600798X_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"S096354830600798X_manual_ref-19","first-page":"230","article-title":"An improved approximation algorithm for the metric uncapacitated facility location problem.","volume":"2337","author":"Sviridenko","year":"2002","journal-title":"Proc. Conference on Integer Programming and Combinatorial Optimization"},{"key":"S096354830600798X_manual_ref-7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24587-2_62"},{"key":"S096354830600798X_manual_ref-1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.1.1"},{"key":"S096354830600798X_manual_ref-12","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"S096354830600798X_manual_ref-18","unstructured":"[18] Steele, J. M. (1997) Probability Theory and Combinatorial Optimization, Vol. 69 of CBMS\u2013NSF Regional Conference Series in Applied Mathematics, SIAM."},{"key":"S096354830600798X_manual_ref-15","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Proc. 5th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization","author":"Mahdian","year":"2002"},{"key":"S096354830600798X_manual_ref-11","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","article-title":"Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP","volume":"50","author":"Jain","year":"2003","journal-title":"J. Assoc. Comput. Mach."},{"key":"S096354830600798X_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"S096354830600798X_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501395423"},{"key":"S096354830600798X_manual_ref-2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.3.253"},{"key":"S096354830600798X_manual_ref-20","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0093472","volume-title":"Probability Theory of Classical Euclidean Optimization Problems","author":"Yukich","year":"1998"},{"key":"S096354830600798X_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"S096354830600798X_manual_ref-10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44867-5_13"},{"key":"S096354830600798X_manual_ref-17","first-page":"265","volume-title":"Proc. 29th Annual ACM Symposium on the Theory of Computation","author":"Shmoys","year":"1997"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830600798X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:24:49Z","timestamp":1750469089000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830600798X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S096354830600798X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830600798x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}