The inverse connected p-median problem on block graphs under various cost functions

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

Annals of Operations Research, 2020, vol. 292, issue 1, No 5, 97-112

Abstract: Abstract We address the problem of modifying vertex weights of a block graph at minimum total cost so that a predetermined set of p connected vertices becomes a connected p-median on the perturbed block graph. This problem is the so-called inverse connected p-median problem on block graphs. We consider the problem on a block graph with uniform edge lengths under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. To solve the problem, we first find an optimality criterion for a set that is a connected p-median. Based on this criterion, we can formulate the problem as a convex or quasiconvex univariate optimization problem. Finally, we develop combinatorial algorithms that solve the problems under the three cost functions in $$O(n\log n)$$ O ( n log n ) time, where n is the number of vertices in the underlying block graph.

Keywords: Combinatorial optimization; Location theory; Connected p-median; Inverse optimization; Block graphs; 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/s10479-020-03651-3 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:292:y:2020:i:1:d:10.1007_s10479-020-03651-3

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

DOI: 10.1007/s10479-020-03651-3

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