## 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 analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, 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.

Original language | English |
---|---|

Pages (from-to) | 441-449 |

Number of pages | 9 |

Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

Publication status | Published - 2005 |

Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: 7 Nov 2005 → 11 Nov 2005 |

## Keywords

- Approximation Algorithms
- Probabilistic Analysis of Algorithms
- Uncapacitated Facilty Location Problem