The Multi-service Location Problems

Hung I. Yu*, Mong Jen Kao, D. T. Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

In this paper, we aim to provide a general study on the framework of Multi-Service Location Problems from a broader perspective and provide systematic methodologies for this category of problems to obtain approximate solutions. In this category of problems, we are to decide the location of a fixed number of facilities providing different types of services, so as to optimize certain distance measures of interest regarding how well the clients are served. Specifically, we are to provide p types of services by locating k ≥ p facilities. Each client has a demanding list for the p types of services, and evaluates its service quality by its service distance, defined as its total transportation cost to those facilities offering the demanded services. Under this framework, we address two kinds of distance measures, the maximum service distance and the average service distance of all clients, and define the p-service k-center problem and the p-service k-median problem, according to the minimax and the minisum criteria, respectively. We develop a general approach for multi-service location problems, and propose a (2p)-approximation and a 4-approximation to the two problems, respectively.

Original languageEnglish
Title of host publicationNew Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
EditorsChuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
PublisherSpringer Verlag
Pages507-515
Number of pages9
ISBN (Print)9789811391897
DOIs
StatePublished - 2019
Event23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
Duration: 20 Dec 201822 Dec 2018

Publication series

NameCommunications in Computer and Information Science
Volume1013
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference23rd International Computer Symposium, ICS 2018
Country/TerritoryTaiwan
CityYunlin
Period20/12/1822/12/18

Keywords

  • k-center
  • k-median
  • Multi-service location

Fingerprint

Dive into the research topics of 'The Multi-service Location Problems'. Together they form a unique fingerprint.

Cite this