An inverse approach to convex ordered median problems in trees |
| |
Authors: | Elisabeth Gassner |
| |
Institution: | 1. Institut f??r Mathematik B, Technische Universit?t Graz, Steyrergasse 30, 8010, Graz, Austria
|
| |
Abstract: | The convex ordered median problem is a generalization of the median, the k-centrum or the center problem. The task of the associated inverse problem is to change edge lengths at minimum cost such
that a given vertex becomes an optimal solution of the location problem, i.e., an ordered median. It is shown that the problem
is NP-hard even if the underlying network is a tree and the ordered median problem is convex and either the vertex weights are
all equal to 1 or the underlying problem is the k-centrum problem. For the special case of the inverse unit weight k-centrum problem a polynomial time algorithm is developed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|