Facility location and the analysis of algorithms through factor-revealing programs
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/16633 |
| _version_ | 1826212936505360384 |
|---|---|
| author | Mahdian, Mohammad, 1976- |
| author2 | Daniel A. Spielman. |
| author_facet | Daniel A. Spielman. Mahdian, Mohammad, 1976- |
| author_sort | Mahdian, Mohammad, 1976- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. |
| first_indexed | 2024-09-23T15:40:30Z |
| format | Thesis |
| id | mit-1721.1/16633 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:40:30Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/166332019-04-10T22:21:37Z Facility location and the analysis of algorithms through factor-revealing programs Mahdian, Mohammad, 1976- Daniel A. Spielman. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. Includes bibliographical references (p. 225-241). This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. In the metric uncapacitated facility location problem (UFLP), we are given a set of clients, a set of facilities, an opening cost for each facility, and a connection cost between each client and each facility satisfying the metric inequality. The objective is to open a subset of facilities and connect each client to an open facility so that the total cost of opening facilities and connecting clients to facilities is minimized. As the UFLP is NP-hard, much effort has been devoted to designing approximation algorithms for it. As our main result, we introduce a method called dual fitting and use it in conjunction with factor-revealing programs to obtain improved approximation algorithms for the UFLP. Our best algorithm achieves an approximation factor of 1.52 (currently the best known factor) and runs in quasilinear time. We demonstrate the versatility of our techniques by using them to analyze the approximation factors of a cycle cover algorithm and a Steiner packing algorithm, as well as the competitive factor of an online buffer management algorithm. We also use our algorithms and other techniques to improve the approximation factors of several variants of the UFLP. In particular, we introduce the notion of bifactor approximate reductions and use it to derive a 2-approximation for the soft-capacitated FLP. Finally, we consider the UFLP in a game-theoretic setting and prove tight bounds on schemes for dividing up the cost of a solution among players. Our result combined with the scheme proposed by Pal and Tardos shows that 1/3 is the best possible approximation factor of any cross-monotonic cost-sharing scheme for the UFLP. Our proof uses a novel technique that we apply to several other optimization problems. by Mohammad Mahdian. Ph.D. 2005-05-17T14:44:30Z 2005-05-17T14:44:30Z 2004 2004 Thesis http://hdl.handle.net/1721.1/16633 56020633 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 241 p. 1875953 bytes 1799081 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Mahdian, Mohammad, 1976- Facility location and the analysis of algorithms through factor-revealing programs |
| title | Facility location and the analysis of algorithms through factor-revealing programs |
| title_full | Facility location and the analysis of algorithms through factor-revealing programs |
| title_fullStr | Facility location and the analysis of algorithms through factor-revealing programs |
| title_full_unstemmed | Facility location and the analysis of algorithms through factor-revealing programs |
| title_short | Facility location and the analysis of algorithms through factor-revealing programs |
| title_sort | facility location and the analysis of algorithms through factor revealing programs |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/16633 |
| work_keys_str_mv | AT mahdianmohammad1976 facilitylocationandtheanalysisofalgorithmsthroughfactorrevealingprograms |