Solving nonconvex planar location problems by finite dominating sets

  • It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed epsilon - to polynomial approximation algorithms with accuracy epsilon for solving the general model considered in this paper.

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Emilio Carrizosa, Horst W. Hamacher, Rolf Klein, Stefan Nickel
URN (Permalink):urn:nbn:de:hbz:386-kluedo-9407
Schriftenreihe (Bandnummer):Berichte des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik (ITWM Report) (18)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2000
Jahr der Veröffentlichung:2000
Veröffentlichende Institution:Fraunhofer-Institut für Techno- und Wirtschaftsmathematik
Datum der Publikation (Server):18.02.2000
Freies Schlagwort / Tag:Approximation ; Continuous Location ; Finite Dominating Sets ; Greedy Algorithm; Polyhedral Gauges ; Sandwich Algorithm
Fachbereiche / Organisatorische Einheiten:Fraunhofer (ITWM)
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $