Topological stability of kinetic k-centers

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Downloads (Pure)

Uittreksel

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.

Originele taal-2Engels
TitelWALCOM
SubtitelAlgorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings
RedacteurenShin-ichi Nakano, Gautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya
Plaats van productieCham
UitgeverijSpringer
Pagina's43-55
Aantal pagina's13
ISBN van elektronische versie978-3-030-10564-8
ISBN van geprinte versie978-3-030-10563-1
DOI's
StatusGepubliceerd - 2019
Evenement13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019 - Guwahati, India
Duur: 27 feb 20192 mrt 2019

Publicatie series

NaamLecture Notes in Computer Science
Volume11355
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019
LandIndia
StadGuwahati
Periode27/02/192/03/19

Vingerafdruk

Kinetics
Upper and Lower Bounds
Radius
P-point
Center Problem
Polynomial time
Optimal Solution
Unstable
Polynomials
Cover
Metric
Optimization
Model

Citeer dit

van der Hoog, I., van Kreveld, M., Meulemans, W., Verbeek, K., & Wulms, J. (2019). Topological stability of kinetic k-centers. In S. Nakano, G. K. Das, P. S. Mandal, & K. Mukhopadhyaya (editors), WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings (blz. 43-55). (Lecture Notes in Computer Science; Vol. 11355). Cham: Springer. https://doi.org/10.1007/978-3-030-10564-8_4
van der Hoog, Ivor ; van Kreveld, Marc ; Meulemans, Wouter ; Verbeek, Kevin ; Wulms, Jules. / Topological stability of kinetic k-centers. WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. redacteur / Shin-ichi Nakano ; Gautam K. Das ; Partha S. Mandal ; Krishnendu Mukhopadhyaya. Cham : Springer, 2019. blz. 43-55 (Lecture Notes in Computer Science).
@inproceedings{d55d6df481da482d9d5ebf6fda4b6110,
title = "Topological stability of kinetic k-centers",
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.",
keywords = "Facility location, Stability analysis, Time-varying data",
author = "{van der Hoog}, Ivor and {van Kreveld}, Marc and Wouter Meulemans and Kevin Verbeek and Jules Wulms",
year = "2019",
doi = "10.1007/978-3-030-10564-8_4",
language = "English",
isbn = "978-3-030-10563-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "43--55",
editor = "Shin-ichi Nakano and Das, {Gautam K.} and Mandal, {Partha S.} and Krishnendu Mukhopadhyaya",
booktitle = "WALCOM",
address = "Germany",

}

van der Hoog, I, van Kreveld, M, Meulemans, W, Verbeek, K & Wulms, J 2019, Topological stability of kinetic k-centers. in S Nakano, GK Das, PS Mandal & K Mukhopadhyaya (redactie), WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. Lecture Notes in Computer Science, vol. 11355, Springer, Cham, blz. 43-55, Guwahati, India, 27/02/19. https://doi.org/10.1007/978-3-030-10564-8_4

Topological stability of kinetic k-centers. / van der Hoog, Ivor; van Kreveld, Marc; Meulemans, Wouter; Verbeek, Kevin; Wulms, Jules.

WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. redactie / Shin-ichi Nakano; Gautam K. Das; Partha S. Mandal; Krishnendu Mukhopadhyaya. Cham : Springer, 2019. blz. 43-55 (Lecture Notes in Computer Science; Vol. 11355).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - Topological stability of kinetic k-centers

AU - van der Hoog, Ivor

AU - van Kreveld, Marc

AU - Meulemans, Wouter

AU - Verbeek, Kevin

AU - Wulms, Jules

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Facility location

KW - Stability analysis

KW - Time-varying data

UR - http://www.scopus.com/inward/record.url?scp=85062680763&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-10564-8_4

DO - 10.1007/978-3-030-10564-8_4

M3 - Conference contribution

AN - SCOPUS:85062680763

SN - 978-3-030-10563-1

T3 - Lecture Notes in Computer Science

SP - 43

EP - 55

BT - WALCOM

A2 - Nakano, Shin-ichi

A2 - Das, Gautam K.

A2 - Mandal, Partha S.

A2 - Mukhopadhyaya, Krishnendu

PB - Springer

CY - Cham

ER -

van der Hoog I, van Kreveld M, Meulemans W, Verbeek K, Wulms J. Topological stability of kinetic k-centers. In Nakano S, Das GK, Mandal PS, Mukhopadhyaya K, redacteurs, WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings. Cham: Springer. 2019. blz. 43-55. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-10564-8_4