Further Study on Reverse 1-Center Problem on Trees

Ali Reza Sepasian and Javad Tayyebi ()
Additional contact information
Ali Reza Sepasian: Faculty of Basic Science, Department of Mathematics, Fasa University, Fasa, Iran
Javad Tayyebi: Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran

Asia-Pacific Journal of Operational Research (APJOR), 2020, vol. 37, issue 06, 1-18

Abstract: This paper studies two types of reverse 1-center problems under uniform linear cost function where edge lengths are allowed to reduce. In the first type, the aim is that the objective value is bounded by a prescribed fixed value p at minimum cost. The aim of the other is to improve the objective value as much as possible within a given budget. An algorithm based on dynamic programming is proposed to solve the first problem in linear time. Then, this algorithm is applied as a subroutine to design an algorithm to solve the second type of the problem in O(nlog(nK)) time in which K is a fixed number dependent on the problem parameters. Under the similarity assumption, this algorithm has a better complexity than the Nguyen algorithm (2013) with quadratic-time complexity. Some numerical experiments are conducted to validate this fact in practice.

Keywords: 1-Center problem; reverse optimization; trees; complexity (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595920500347
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:37:y:2020:i:06:n:s0217595920500347

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595920500347

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 ().