Return to search

Facility location and the analysis of algorithms through factor-revealing programs

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.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/16633
Date January 2004
CreatorsMahdian, Mohammad, 1976-
ContributorsDaniel A. Spielman., Massachusetts Institute of Technology. Dept. of Mathematics., Massachusetts Institute of Technology. Dept. of Mathematics.
PublisherMassachusetts Institute of Technology
Source SetsM.I.T. Theses and Dissertation
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Format241 p., 1875953 bytes, 1799081 bytes, application/pdf, application/pdf, application/pdf
RightsM.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

Page generated in 0.0034 seconds