  


Improved approximation algorithms for the facility location problems with linear/submodular penalty
Yu Li(liyubjutgmail.com) Abstract: We consider the facility location problem with submodular penalty (FLPSP) and the facility location problem with linear penalty (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalty, extending the recent result of Geunes et al. [12] with linear penalty. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their submodular penalty counterparts. Specifically, any LPbased \alphaapproximation for the original covering problem can be leveraged to obtain an 1/(1e^{1/\alpha})approximation algorithm for the counterpart with submodular penalty. Consequently, any LPbased approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the submodular penalty counterpart. Second, by exploiting some special properties of FLP, we present an LP rounding algorithm which has the currently best 2approximation ratio over the previously best 2:50 by Hayrapetyan et al. [14] for the FLPSP and another LP rounding algorithm which has the currently best 1:5148approximation ratio over the previously best 1:853 by Xu and Xu [29] for the FLPLP, respectively. Keywords: Approximation algorithm Facility location problem LP rounding Submodular function Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Working Paper Series 2012, Faculty of Business Administration, University of New Brunswick, Canada Download: [PDF] Entry Submitted: 02/04/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  