Inverse p-median problems with variable edge lengths

Fahimeh Baroughi Bonab (), Rainer Burkard () and Elisabeth Gassner ()

Mathematical Methods of Operations Research, 2011, vol. 73, issue 2, 263-280

Abstract: The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly $${\mathcal{NP}}$$ -hard on general graphs and weakly $${\mathcal{NP}}$$ -hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm. Copyright Springer-Verlag 2011

Keywords: Location problem; Inverse optimization; p-median; Complexity analysis (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-011-0346-5 (text/html)
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:spr:mathme:v:73:y:2011:i:2:p:263-280

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

DOI: 10.1007/s00186-011-0346-5

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().