Top

Journal of Combinatorial Optimization

Published in:

01-04-2014

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

Authors: Yu Li, Donglei Du, Naihua Xiu, Dachuan Xu

Published in: Journal of Combinatorial Optimization | Issue 3/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.

previous article Order consolidation for hierarchical product lines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Charikar M, Khuller S, Mount DM, Naraasimban G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642–651

Chudak FA, Nagano K (2007) Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization. In: Proceedings of SODA, pp 79–88

Du D, Lu R, Xu D (2012) A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63:191–200 CrossRefMATHMathSciNet

Fujishige S (2005) Submodular functions and optimization, 2nd edn. Annals of discrete mathematics, vol 58. Elsevier, Amsterdam MATH

Geunes J, Levi R, Romeijn HE, Shmoys DB (2011) Approximation algorithms for supply chain planning and logistics problems with market choice. Math Program 130:85–106 CrossRefMATHMathSciNet

Hayrapetyan A, Swamy C, Tardös E (2005) Network design for information networks. In: Proceedings of SODA, pp 933–942

Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48:274–296 CrossRefMATHMathSciNet

Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795–824 CrossRefMathSciNet

Li S (2011) A 1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, part II, pp 77–88

Mahdian M, Ye Y, Zhang J (2006) Improved approximation algorithms for metric facility location problems. SIAM J Comput 36:411–432 CrossRefMATHMathSciNet

Shmoys DB, Tardös E, Aardal KI (1997) Approximation algorithms for facility location problems (extended abstract). In: Proceedings of STOC, pp 265–274

Thorup M (2003) Quick and good facility location. In: Proceedings of SODA, pp 178–185

Xu G, Xu J (2005) An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Inf Process Lett 94:119–123 CrossRefMATH

Xu G, Xu J (2008) An improved approximation algorithm for uncapacitated facility location problem with penalties. J Comb Optim 17:424–436 CrossRef

Title: A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
Authors: Yu Li
Donglei Du
Naihua Xiu
Dachuan Xu
Publication date: 01-04-2014
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2014
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9540-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2014

Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

Order consolidation for hierarchical product lines

On the performance of Scatter Search for post-enrolment course timetabling problems

Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles

Are there more almost separable partitions than separable partitions?

An approximation algorithm for k-center problem on a convex polygon

Premium Partner