Topological stability of kinetic k-centers

Ivor van der Hoog, Marc van Kreveld, Wouter Meulemans, Kevin Verbeek, Jules Wulms

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

24 Downloads (Pure)

Abstract

We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For k = 2 we provide tight bounds, and for small we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings
EditorsShin-ichi Nakano, Gautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya
Place of PublicationCham
PublisherSpringer
Pages43-55
Number of pages13
ISBN (Electronic)978-3-030-10564-8
ISBN (Print)978-3-030-10563-1
DOIs
Publication statusPublished - 2019
Event13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019 - Guwahati, India
Duration: 27 Feb 20192 Mar 2019

Publication series

NameLecture Notes in Computer Science
Volume11355
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019
CountryIndia
CityGuwahati
Period27/02/192/03/19

Keywords

  • Facility location
  • Stability analysis
  • Time-varying data

Fingerprint Dive into the research topics of 'Topological stability of kinetic k-centers'. Together they form a unique fingerprint.

Cite this