Up- and downgrading the euclidean 1-median problem and knapsack Voronoi diagrams

Frank Plastria ()
Additional contact information
Frank Plastria: Vrije Universiteit Brussel

Annals of Operations Research, 2016, vol. 246, issue 1, No 13, 227-251

Abstract: Abstract We consider the 1-median problem with euclidean distances with uncertainty in the weights, expressed as possible changes within given bounds and a single budget constraint on the total cost of change. The upgrading (resp. downgrading) problem consists of minimizing (resp. maximizing) the optimal 1-median objective value over these weight changes. The upgrading problem is shown to belong to the family of continuous single facility location-allocation problems, whereas the downgrading problem reduces to a convex but highly non-differentiable optimization problem. Several structural properties of the optimal solution are proven for both problems, using novel planar partitions, the knapsack Voronoi diagrams, and lead to polynomial time solution algorithms.

Keywords: Fermat–Weber problem; Facility location; Upgrading; Downgrading; Nonlinear optimization; Non-convex optimization; Knapsack Voronoi diagram; Polynomial algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-014-1587-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:246:y:2016:i:1:d:10.1007_s10479-014-1587-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1587-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().