Some robust inverse median problems on trees with interval costs

Le Xuan Dai (), Kien Trung Nguyen (), Le Phuong Thao () and Pham Thi Vui ()
Additional contact information
Le Xuan Dai: Vietnam National University Ho Chi Minh City (VNU-HCM)
Kien Trung Nguyen: Can Tho University
Le Phuong Thao: Can Tho University
Pham Thi Vui: Can Tho University

Computational Management Science, 2024, vol. 21, issue 2, No 5, 25 pages

Abstract: Abstract We address the problem of modifying vertex weights of a tree in such an optimal way that a given facility (vertex) becomes a 1-median in the modified tree. Here, each modifying cost receive any value within an interval. As the costs ar.e not exactly known, we apply the concept of absolute robust and minmax regret criteria to measure the cost functions. We first consider the absolute robust inverse 1-median problem with sum objective function. The duality of the problem helps to know the convexity of the induced univariate minimization problem. Based on the convexity, an $$O(n\log ^{2} n)$$ O ( n log 2 n ) time algorithm is developed, where n is the number of vertices on the underlying tree. We also apply the minmax regret criteria to the uncertain inverse 1-median problem with Chebyshev norm and bottleneck Hamming distance. It is shown that in the optimal solution there exists exactly one cost coefficient attaining the upper bound and the others attaining their lower bounds. Hence, we develop strongly polynomial-time algorithms for the problems based on this special property.

Keywords: Location problem; Inverse optimization; Robust optimization; Minmax regret; Tree; 90B10; 90B80; 90C27 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-024-00522-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:comgts:v:21:y:2024:i:2:d:10.1007_s10287-024-00522-1

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-024-00522-1

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().