Reverse 1-centre problem on trees under convex piecewise-linear cost function. (4th March 2023)

• Record Type: Journal Article
• Authors: Tayyebi, Javad; Reza Sepasian, Ali
• Is Part Of: Optimization. Volume 72:Number 3(2023)
• Page Start: 843
• Page End: 860
• Publication Date: 2023-03-04
• Subjects: 1-centre problem -- reverse optimization -- trees -- efficient algorithms -- minimum cost flow problem; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2021.1995730
• Languages: English
• ISSNs: 0233-1934

Abstract

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.