A linear time algorithm for the p-maxian problem on trees with distance constraint

Trung Kien Nguyen (), Nguyen Thanh Hung () and Huong Nguyen-Thu ()
Additional contact information
Trung Kien Nguyen: Teacher College, Can Tho University
Nguyen Thanh Hung: Teacher College, Can Tho University
Huong Nguyen-Thu: Teacher College, Can Tho University

Journal of Combinatorial Optimization, 2020, vol. 40, issue 4, No 11, 1030-1043

Abstract: Abstract This paper concerns the p-maxian problem on trees with an upper bound on the distance of new facilities. We first consider the case $$p = 2$$ p = 2 and show that the optimal objective is obtained if the constraint holds with equality. By this result, we further explore the characteristic of the optimal solution, which helps to develop a linear time algorithm to solve the constrained 2-maxian problem. The result can be extended to the constrained p-maxian on trees based on the nestedness property. We also discuss the constrained p-maxian problem on trees in relation to the unconstrained p-maxian problem and the 1-maxian problem on the underlying tree.

Keywords: Location problem; Maxian problem; Tree; Convex; 90B10; 90B80; 90C27 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00650-9 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:jcomop:v:40:y:2020:i:4:d:10.1007_s10878-020-00650-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00650-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().