Median problems with positive and negative weights on cycles and cacti

Rainer E. Burkard () and Johannes Hatzl ()
Additional contact information
Rainer E. Burkard: Graz University of Technology
Johannes Hatzl: Graz University of Technology

Journal of Combinatorial Optimization, 2010, vol. 20, issue 1, No 2, 27-46

Abstract: Abstract This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed. The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of $\mathcal{O}(n^{2})$ .

Keywords: Location problems; Median problems; Obnoxious facilities (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9187-4 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:jcomop:v:20:y:2010:i:1:d:10.1007_s10878-008-9187-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9187-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().