Reverse 1-centre problem on trees under convex piecewise-linear cost function

ABSTRACT

Given a network as well as a prescribed vertex s in which a facility is located, the aim of solving reverse 1-centre problems is to decrease edge lengths under a budget constraint in a way that the maximum distance between s and the other vertices is minimized. This paper considers the reverse 1-centre problem on general tree networks with weights associated to vertices under a convex piecewise-linear cost function. It is shown that the problem can be transformed into a parametric minimum cost flow problem. A polynomial time approximation scheme (PTAS) is first developed using the bisection method. Then, the problem on unweighted trees is investigated. Using sensitivity analysis, a pseudo-polynomial time algorithm is designed. Finally, a hybrid algorithm is developed to obtain an exact solution in polynomial time.

KEYWORDS:

• 1-centre problem
• reverse optimization
• trees
• efficient algorithms
• minimum cost flow problem

Disclosure statement

No potential conflict of interest was reported by the author(s).