The max-sum inverse median location problem on trees with budget constraint

Huong Nguyen-Thu, Kien Trung Nguyen and Nguyen Thanh Toan

Applied Mathematics and Computation, 2024, vol. 460, issue C

Abstract: The theory of inverse location involves modifying parameters in such a way that the total cost is minimized and one/several prespecified facilities become optimal based on these perturbed parameters. When the modifying parameters are grouped into sets, with each group's cost measured under the rectilinear norm and the overall cost measured under the Chebyshev norm, the resulting problem is known as the max-sum inverse location problem. This paper addresses the max-sum inverse median location problem on trees with a budget constraint, where the objective is to modify the vertex weights so that a specified vertex becomes a 1-median, while minimizing the max-sum objective within the available budget. To solve this problem, a uni-variable optimization problem is first induced, where the objective function for each specified value of the variable can be obtained through a continuous knapsack problem. Leveraging the monotonicity of the cost function, a combinatorial algorithm is developed, which solves the problem in O(nlog⁡n) time, where n denotes the number of vertices present in the tree.

Keywords: Inverse optimization; Budget constraint; Median problem; Tree graph; Knapsack problem (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323004654
Full text for ScienceDirect subscribers only

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:eee:apmaco:v:460:y:2024:i:c:s0096300323004654

DOI: 10.1016/j.amc.2023.128296

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().