nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.04.2014

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

verfasst von: Yu Li, Donglei Du, Naihua Xiu, Dachuan Xu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Order consolidation for hierarchical product lines

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
verfasst von: Yu Li
Donglei Du
Naihua Xiu
Dachuan Xu
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9540-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2014

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

The Pfaffian property of Cartesian products of graphs

Star list chromatic number of planar subcubic graphs

On the total outer-connected domination in graphs

On the approximability of positive influence dominating set in social networks

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