A polynomial method for the pos/neg weighted 3-median problem on a tree |
| |
Authors: | Rainer E Burkard Jafar Fathali |
| |
Institution: | (1) Institute of Mathematics B, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria;(2) Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran |
| |
Abstract: | Let a connected undirected graph G = (V, E) be given. In the classical p-median problem we want to find a set X containing p points in G such that the sum of weighted distances from X to all vertices in V is minimized. We consider the semi-obnoxious case where every vertex has either a positive or negative weight. In this case
we have two different objective functions: the sum of the minimum weighted distances from X to all vertices and the sum of the weighted minimum distances. In this paper we show that for the case p = 3 an optimal solution for the second model in a tree can be found in O(n
5) time. If the 3-median is restricted to vertices or if the tree is a path then the complexity can be reduced to O(n
3).
This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich
Diskrete Optimierung. |
| |
Keywords: | Location theory p-median problem Obnoxious facilities |
本文献已被 SpringerLink 等数据库收录! |
|