Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
verfasst von : Sin-Shuen Cheung
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.