University of Twente Student Theses
Perturbation resilience for the facility location problem
Tijink, M.B. (2017) Perturbation resilience for the facility location problem.
|
PDF
1MB |
| Abstract: | Several NP-hard problems, e.g. k-means clustering, are solved very quickly and near optimality for practical instances, even though there are known worst-cases from a theoretical perspective. These worst-cases do not seem to appear in practice. There even is a saying; “Clustering is either easy or pointless”, indicating that the difficulty of these problems is only a theoretical concern. Several approaches to formalize this saying, by assuming that instances have a natural stability property in practice, recently proved to be successful in closing the gap between theory and practice. In this thesis we look at the facility location problem, which is NP-hard. We add the γ-perturbation resilience assumption, which requires that the instance must allow small perturbations of all costs in the instance without changing its optimal solution. Many instances in practice likely already satisfy this assumption, so we focus on the theoretical impact of this assumption. We found several consequences this assumption; local search algorithms will always result in the optimal solution, for γ ≥ 3, and may not give the optimal solution for all γ < 3. We also show that several greedy algorithms do not work either to solve the facility location problem with the γ-perturbation resilience assumption, even for high γ. A relation between this assumption and approximation algorithms seems obvious, but we prove that this relation is false. Finally, we show that, for small γ, the existence of an efficient algorithm to solve the facility location problem with the γ-perturbation resilience assumption implies that RP = NP. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/73299 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page