Title :
An algorithm for the facility location problems
Author :
An, Fengxian ; Wang, Zongyao ; Wang, Dongdong
Author_Institution :
Fac. of Math. & Phys., Huaiyin Inst. of Technol., Huaiyin, China
Abstract :
Variants of the facility location problem have been studied extensively in the operations research and management science literatures. In this paper, we present a new analysis method of a simple greedy algorithm for the uncapacitated facility location problem. We achieve an approximation guarantee of 1.5749 better than 1.853, which is the approximation ratio provided by the combinatorial approximation algorithm due to Charikar and Guha.
Keywords :
approximation theory; combinatorial mathematics; computational complexity; facility location; greedy algorithms; management science; combinatorial approximation algorithm; facility location problems; greedy algorithm; management science; operations research; Algorithm design and analysis; Approximation algorithms; Asia; Automatic control; Costs; Informatics; Mathematics; Physics; Robot control; Robotics and automation; approximation algorithm; cost scaling; facility location; greedy improvement;
Conference_Titel :
Informatics in Control, Automation and Robotics (CAR), 2010 2nd International Asia Conference on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-5192-0
Electronic_ISBN :
1948-3414
DOI :
10.1109/CAR.2010.5456780
