TY - CONF

T1 - Greedy strikes back

T2 - Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms

AU - Guha, Sudipto

AU - Khuller, Samir

N1 - Funding Information:
* A preliminary version of this paper appeared in the Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998). ²Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: sudipto@cs.stanford.edu. ³ Research supported by NSF CAREER Award CCR-9501355. E-mail: samir@cs.umd.edu.
Copyright:
Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 1998

Y1 - 1998

N2 - A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. This problem is commonly referred to as the uncapacitated facility location problem. Applications to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos and Aardal. We show that a simple greedy heuristic combined with the Shmoys, Tardos and Aardal algorithm, can be used to derive a better approximation guarantee. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is Max SNP-hard. However, the inapproximability constants derived from the Max SNP hardness are very close to one. By relating this problem to Set Cover, we can prove a better lower bound on the best possible approximation ratio.

AB - A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. This problem is commonly referred to as the uncapacitated facility location problem. Applications to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos and Aardal. We show that a simple greedy heuristic combined with the Shmoys, Tardos and Aardal algorithm, can be used to derive a better approximation guarantee. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is Max SNP-hard. However, the inapproximability constants derived from the Max SNP hardness are very close to one. By relating this problem to Set Cover, we can prove a better lower bound on the best possible approximation ratio.

UR - http://www.scopus.com/inward/record.url?scp=0032280078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032280078&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032280078

SP - 649

EP - 657

Y2 - 25 January 1998 through 27 January 1998

ER -