The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights

Tran Hoai Ngoc Nhan (), Kien Trung Nguyen and Huong Nguyen-Thu ()
Additional contact information
Tran Hoai Ngoc Nhan: Faculty of Basic Science, Vinh Long University of Technology Education, Vinh Long, Vietnam
Kien Trung Nguyen: Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
Huong Nguyen-Thu: Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 03, 1-17

Abstract: The classical reverse 1-median problem on trees is to adjust the edge lengths within a budget so as to reduce the 1-median function at a predetermined vertex as much as possible. This paper concerns the corresponding problem with uncertain vertex weights presented by linear functions. Moreover, we use the minmax regret criterion to measure the maximum loss of a feasible solution with respect to the worst-case scenario. The regarding problem is called the minmax regret reverse 1-median problem on trees. We first partition the set of scenarios into parts such that the optimal solution of the corresponding reverse 1-median problem does not change in each part. Then the problem can be reformulated as the minimization of a quadratic number of affine linear functions. We finally develop a greedy algorithm that solves the problem in O(n3) time where n is the number of vertices in the underlying tree.

Keywords: Location problem; Reverse optimization; Uncertainty; Minmax regret; Tree (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922500336
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:03:n:s0217595922500336

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922500336

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().