Approximation algorithms for Median Hub Location Problems

Marcelo P. L. Benedito () and Lehilton L. C. Pedrosa ()
Additional contact information
Marcelo P. L. Benedito: University of Campinas
Lehilton L. C. Pedrosa: University of Campinas

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 4, 375-401

Abstract: Abstract In Hub Location Problems, an input is composed of sets of clients, locations and a pairs of clients; a solution is a subset of locations to open hubs and an assignment for each pair of clients to a route starting in the first client, passing through one or more hubs and ending in the second client. The objective is to find a solution that minimizes the length of all routes plus the cost of opening hubs. The currently known approximation algorithms consider only the case in which the set of hubs is given as part of the input and the problem is assigning clients to hubs. For a metric space setting, this work presents the first constant-factor approximation algorithms for the problem of, simultaneously, selecting hubs and allocating clients. A few variants are considered, depending on whether the number of open hubs is given in the input or a client must be assigned to a single hub. In particular, we give an LP-rounding $$2.48$$ 2.48 -approximation algorithm for the Single-Allocation Median Hub Location Problem, using a new formulation and exploiting its symmetries.

Keywords: Approximation algorithm; Hub Location Problem; LP-rounding (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00386-1 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:38:y:2019:i:2:d:10.1007_s10878-019-00386-1

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

DOI: 10.1007/s10878-019-00386-1

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