An inverse approach to convex ordered median problems in trees

An inverse approach to convex ordered median problems in trees

0.00 Avg rating0 Votes
Article ID: iaor2012600
Volume: 23
Issue: 2
Start Page Number: 261
End Page Number: 273
Publication Date: Feb 2012
Journal: Journal of Combinatorial Optimization
Authors:
Keywords: optimization, heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.