Approximation algorithm for the kinetic robust k-center problem

Redirect to:

• Approximation algorithm for the kinetic robust \(k\)-center problem

DOI10.1016/J.COMGEO.2010.01.001MaRDI QIDQ982946zbMATH OpenOpenAlexFDO

Authors Sorelle A. Friedler, David M. Mount

Publication date 28 July 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2010.01.001

zbMATH Keywords

\(k\)-center problemalgorithmclusteringexponential complexitykinetic data structuresrobust statistics

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Numerical mathematical programming methods (65K05) Stochastic programming (90C15)

Recommendations

• Kinetic 2-centers in the black-box model
• Topological stability of kinetic \(k\)-centers
• Topological stability of kinetic \(k\)-centers
• Clustering motion
• Kinetic clustering of points on the line

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A heuristic for the p-center problem in graphs
• Algorithms for facility location problems with outliers. (Extended abstract)
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Approximate range searching: The absolute model
• Approximation algorithms for NP-hard problems.
• Clustering motion
• Clustering to minimize the maximum intercluster distance
• Data Structures for Mobile Data
• Deformable spanners and applications
• Fast algorithms for collision and proximity problems involving moving geometric objects
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• scientific article; zbMATH DE number 1501063 (Why is no real title available?)
• scientific article; zbMATH DE number 194744 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Introduction to algorithms
• On the computational complexity of centers locating in a graph
• Searching dynamic point sets in spaces with bounded doubling dimension
• Some dynamic computational geometry problems
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• The Kinetic Facility Location Problem
• Voronoi Diagrams of Moving Points

Cited in

(12)

• Clustering motion
• Topological stability of kinetic \(k\)-centers
• A scaleable projection-based branch-and-cut algorithm for the \(p\)-center problem
• Kinetic clustering of points on the line
• Temporal clustering
• scientific article; zbMATH DE number 7278033 (Why is no real title available?)
• Kinetic 2-centers in the black-box model
• Topological stability of kinetic \(k\)-centers
• Constrained \(k\)-center and movement to independence
• Kinetic Maintenance of Mobile k-Centres on Trees
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• Mixed-integer linear programming approaches for nested p-center problems with absolute and relative regret objectives

This page was built for publication: Approximation algorithm for the kinetic robust \(k\)-center problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q982946)