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 NPhard problems, e.g. kmeans clustering, are solved very quickly and near optimality for practical instances, even though there are known worstcases from a theoretical perspective. These worstcases 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 NPhard. 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:  http://purl.utwente.nl/essays/73299 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page