Optimization Online


Improved approximation algorithms for the facility location problems with linear/submodular penalty

Yu Li(liyubjut***at***gmail.com)
Donglei Du(ddu***at***unb.ca)
Naihua Xiu(nhxiu***at***center.njtu.edu.cn)
Dachuan Xu(xudc***at***bjut.edu.cn)

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. Speci fically, any LP-based \alpha-approximation for the original covering problem can be leveraged to obtain an 1/(1-e^{-1/\alpha})-approximation algorithm for the counterpart with submodular penalty. Consequently, any LP-based 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 2-approximation 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:5148-approximation 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
Entry Accepted: 02/04/2012
Entry Last Modified: 02/04/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society