Multi-Stage Facility Location Problems with Transient Agents

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the 37th AAAI Conference on Artificial Intelligence
EditorsBrian Williams, Yiling Chen, Jennifer Neville
Place of PublicationWashington, DC
PublisherAAAI Press
Pages5850-5857
ISBN (Electronic)978-1-57735-880-0 (set)
Publication statusPublished - 2023

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
Number5
Volume37
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

Title37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23)
LocationWalter E. Washington Convention Center
PlaceUnited States
CityWashington
Period7 - 14 February 2023

Abstract

We study various models for the one-dimensional multi-stage facility location problems with transient agents, where a transient agent arrives in some stage and stays for a number of consecutive stages. In the problems, we need to serve each agent in one of their stages by determining the location of the facility at each stage. In the first model, we assume there is no cost for moving the facility across the stages. We focus on optimal algorithms to minimize both the social cost objective, defined as the total distance of all agents to the facility over all stages, and the maximum cost objective, defined as the max distance of any agent to the facility over all stages. For each objective, we give a slice-wise polynomial (XP) algorithm (i.e., solvable in mƒ(k) for some fixed parameter k and computable function ƒ, where m is the input size) and show that there is a polynomial-time algorithm when a natural first-come-first-serve (FCFS) order of agent serving is enforced. We then consider the mechanism design problem, where the agents' locations and arrival stages are private, and design a group strategy-proof mechanism that achieves good approximation ratios for both objectives and settings with and without FCFS ordering. In the second model, we consider the facility's moving cost between adjacent stages under the social cost objective, which accounts for the total moving distance of the facility. Correspondingly, we design XP (and polynomial time) algorithms and a group strategy-proof mechanism for settings with or without the FCFS ordering. © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org).

Citation Format(s)

Multi-Stage Facility Location Problems with Transient Agents. / Wang, Xuezhen; Chau, Vincent; Chan, Hau et al.
Proceedings of the 37th AAAI Conference on Artificial Intelligence. ed. / Brian Williams; Yiling Chen; Jennifer Neville. Washington, DC: AAAI Press, 2023. p. 5850-5857 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 37, No. 5).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review