File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-031-22105-7_14
- Scopus: eid_2-s2.0-85148014661
- WOS: WOS:000916958900014
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Fully Dynamic k-Center Clustering with Outliers
Title | Fully Dynamic <i>k</i>-Center Clustering with Outliers |
---|---|
Authors | |
Keywords | Approximation algorithm Clustering Fully dynamic |
Issue Date | 1-Jan-2023 |
Publisher | Springer |
Abstract | We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. |
Persistent Identifier | http://hdl.handle.net/10722/338115 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, THH | - |
dc.contributor.author | Lattanzi, S | - |
dc.contributor.author | Sozio, M | - |
dc.contributor.author | Wang, B | - |
dc.date.accessioned | 2024-03-11T10:26:22Z | - |
dc.date.available | 2024-03-11T10:26:22Z | - |
dc.date.issued | 2023-01-01 | - |
dc.identifier.isbn | 978-3-031-22104-0 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/338115 | - |
dc.description.abstract | We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input. | - |
dc.language | eng | - |
dc.publisher | Springer | - |
dc.relation.ispartof | Lecture Notes in Computer Science | - |
dc.subject | Approximation algorithm | - |
dc.subject | Clustering | - |
dc.subject | Fully dynamic | - |
dc.title | Fully Dynamic <i>k</i>-Center Clustering with Outliers | - |
dc.type | Conference_Paper | - |
dc.identifier.doi | 10.1007/978-3-031-22105-7_14 | - |
dc.identifier.scopus | eid_2-s2.0-85148014661 | - |
dc.identifier.volume | 13595 | - |
dc.identifier.spage | 150 | - |
dc.identifier.epage | 161 | - |
dc.identifier.eissn | 1611-3349 | - |
dc.identifier.isi | WOS:000916958900014 | - |
dc.publisher.place | CHAM | - |
dc.identifier.eisbn | 978-3-031-22105-7 | - |
dc.identifier.issnl | 0302-9743 | - |