Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Approximations for the Max k-Colored Clustering Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem

Author : Sin-Shuen Cheung

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In this paper we consider natural generalizations of the facility location problem and the joint replenishment problem in which the opening cost of facilities and the ordering cost over the planning horizon is characterized by a submodular set function in the oracle model. Specifically, we can access the function only through a blackbox that returns the value of the function for a given set. We prove information theoretic lower bounds that these two problems cannot be approximated by any polynomial-time algorithm better than a ratio of \(O(\sqrt{n}/\log ^2{n})\). Moreover, we give \(O(\sqrt{n}\cdot \log n)\)-approximation algorithms for the two problems.

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 "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

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
previous chapter Improved Approximation Algorithm for Fault-Tolerant Facility Placement
next chapter Online Multi-Coloring with Advice
Literature
1.
Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. STOC’97, pp. 265–274. ACM, New York (1997)
2.
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1–25 (2003)CrossRefMATHMathSciNet
3.
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM (JACM) 48(2), 274–296 (2001)CrossRefMATHMathSciNet
4.
Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th Annual IEEE Symposium on Foundations of Computer Science, 1999. FOCS’99, pp. 378–388 (1999)
5.
Gupta, A., Tangwongsan, K.: Simpler analyses of local search algorithms for facility location (2008) arXiv preprint arXiv:​0809.​2554
6.
Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM (JACM) 50(6), 795–824 (2003)CrossRefMathSciNet
7.
Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39(6), 2212–2231 (2010)CrossRefMATHMathSciNet
8.
Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013)CrossRefMATH
9.
10.
Svitkina, Z., Tardos, E.: Facility location with hierarchical facility costs. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. SODA’06,pp. 153–161. ACM, New York (2006)
11.
Hayrapetyan, A., Swamy, C., Tardos, E.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA’05, pp. 933–942. Society for Industrial and Applied Mathematics, Philadelphia (2005)
12.
Chudak, F.A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA’07, pp. 79–88. Society for Industrial and Applied Mathematics, Philadelphia (2007)
13.
Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63(1–2), 191–200 (2012)CrossRefMATHMathSciNet
14.
Cheung, M., Elmachtoub, A.N., Levi, R., Shmoys, D.B.: The submodular joint replenishment problem. Unpublished Manuscript (2013)
15.
Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715–1737 (2011)CrossRefMATHMathSciNet
16.
Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS’09, pp. 671–680 (2009)
17.
Goemans, M.X., Harvey, N.J., Iwata, S., Mirrokni, V.: Approximating submodular functions everywhere. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535–544. Society for Industrial and Applied Mathematics, New York (2009)
18.
Levi, R., Roundy, R., Shmoys, D., Sviridenko, M.: A constant approximation algorithm for the one-warehouse multiretailer problem. Manag. Sci. 54(4), 763–776 (2008)CrossRefMATH
Metadata
Title
The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
Author
Sin-Shuen Cheung
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-18262-9

Electronic ISBN: 978-3-319-18263-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-18263-6_7

Premium Partner

    Image Credits