The absolute quickest 1-center problem on a cycle and its reverse problem

Kien Trung Nguyen ()
Additional contact information
Kien Trung Nguyen: Can Tho University

Annals of Operations Research, 2025, vol. 347, issue 3, No 11, 1473-1491

Abstract: Abstract The concept of the quickest path refers to the path with the minimum transmission time, considering both its length and capacity. We investigate the problem of finding a point on a cycle such that the maximum quickest distance from any vertex to that point is minimized. We refer to this problem as the quickest 1-center problem on cycles. First, we solve the problem on paths in linear time based on the optimality criterion. Then, we address the problem on cycles in $$O(n^2)$$ O ( n 2 ) time by leveraging the solution approach on the induced path in each iteration, where n is the number of vertices. We also consider the problem of reducing the quickest distance objective at a predetermined vertex of a cycle as much as possible by augmenting the edge capacities within a given budget. This problem is called the reverse quickest 1-center problem on cycles. We develop a combinatorial algorithm that solves the problem in $$O(n^2)$$ O ( n 2 ) time by solving each subproblem in linear time.

Keywords: Quickest path; Location problem; Reverse optimization; 1-Center; Cycle; 90B10; 90B80; 90C27 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06361-2 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:annopr:v:347:y:2025:i:3:d:10.1007_s10479-024-06361-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06361-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().