Reverse selective obnoxious center location problems on tree graphs

Roghayeh Etemad and Behrooz Alizadeh ()
Additional contact information
Roghayeh Etemad: Sahand University of Technology
Behrooz Alizadeh: Sahand University of Technology

Mathematical Methods of Operations Research, 2018, vol. 87, issue 3, No 5, 450 pages

Abstract: Abstract In this paper, we investigate a variant of the reverse obnoxious center location problem on a tree graph $$T=(V,E)$$ T = ( V , E ) in which a selective subset of the vertex set V is considered as locations of the existing customers. The aim is to augment or reduce the edge lengths within a given budget with respect to modification bounds until a predetermined undesirable facility location becomes as far as possible from the customer points under the new edge lengths. An $${\mathcal {O}}(|E|^2)$$ O ( | E | 2 ) time combinatorial algorithm is developed for the problem with arbitrary modification costs. For the uniform-cost case, one obtains the improved $${\mathcal {O}}(|E|)$$ O ( | E | ) time complexity. Moreover, optimal solution algorithms with $${\mathcal {O}}(|E|^2)$$ O ( | E | 2 ) and $${\mathcal {O}}(|E|)$$ O ( | E | ) time complexities are proposed for the integer version of the problem with arbitrary and uniform cost coefficients, respectively.

Keywords: Obnoxious center location; Combinatorial optimization; Reverse optimization; Time complexity; 90B80; 90B85; 90C27; 90C35 (search for similar items in EconPapers)
Date: 2018
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/s00186-017-0624-y 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:mathme:v:87:y:2018:i:3:d:10.1007_s00186-017-0624-y

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

DOI: 10.1007/s00186-017-0624-y

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