Loading...
Please wait, while we are loading the content...
Similar Documents
Adapting the Chudak-Shmoys approximation algorithm to the k-level uncapacitated facility location problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Mulder, Jan |
| Copyright Year | 2011 |
| Abstract | Chudak and Shmoys have proposed an (1 + 2/e)-approximation algorithm to the 1-level uncapacitated facility location problem. In this thesis, this approximation algorithm is first extended to the 2-level problem. We prove that under a specific assumption on the structure of the solution of the LP-relaxation, a solution of the 2-level problem can be transformed to an equivalent solution of the 1-level problem. The assumption made is that all positive values that occur in a connected component are equal. Then, the algorithm of Chudak and Shmoys can be applied on the new obtained solution. Thereafter, we show in a similar way that a valid extension of the Chudak and Shmoys to the k-level uncapacitated facility location problem exists under this assumption. For the 1, 2 and 3-level uncapacitated facility location problem, 10,000 small and large problem instances are generated at random and the LP-relaxation is solved. The percentage of fractional solutions that satisfy the assumption made in this thesis decreases when the size of the problem instances increases. However, all the solution to these problem instances have a structure in which all positive values in a connected component have the same denominator. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://repository.tudelft.nl/islandora/object/uuid:337363b1-20fe-4485-9d73-af3a946f9cc1/datastream/OBJ/download |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
