We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem.
- Authors
ABRAHAM D. FLAXMAN; ALAN M. FRIEZE; JUAN CARLOS VERA
- Abstract
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, in practice, 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.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 n 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.
- Subjects
ALGORITHMS; COMBINATORIAL optimization; APPROXIMATION theory; POLYNOMIALS; PROBABILITY theory
- Publication
Combinatorics, Probability & Computing, 2007, Vol 16, Issue 5, p713
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S096354830600798X