Approximation algorithms for clustering with dynamic points

DOI10.4230/LIPICS.ESA.2020.37MaRDI QIDQ5874506zbMATH OpenFDO

Authors Shichuan Deng, Jian Li, Yuval Rabani

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2020.37

zbMATH Keywords

clusteringdynamic pointsmulti-objective optimization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximation algorithms for clustering with dynamic points
• Clustering motion
• Dynamic sum-radii clustering
• Temporal clustering
• Dynamic clustering to minimize the sum of radii

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A constant factor approximation algorithm for fault-tolerant k-median
• A dependent LP-rounding approach for the k-median problem
• A Lottery Model for Center-Type Problems With Outliers
• Algorithms for facility location problems with outliers. (Extended abstract)
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximating k-median with non-uniform capacities
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Approximating k-median via pseudo-approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for minimum norm and ordered optimization problems
• Constant-factor approximation for ordered k-median
• Dependent rounding and its applications to approximation algorithms
• Dynamic facility location via exponential clocks
• Facility location in evolving metrics
• Fault tolerant \(K\)-center problems
• Fault-tolerant facility location
• scientific article; zbMATH DE number 7204578 (Why is no real title available?)
• Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
• Local Search Heuristics for k-Median and Facility Location Problems
• Local-search based approximation algorithms for mobile facility location problems (extended abstract)
• Minimizing movement
• Minimizing movement in mobile facility location problems
• New approaches to multi-objective optimization
• Reducibility among combinatorial problems
• The non-uniform k-center problem
• The ordered \(k\)-median problem: surrogate models and approximation algorithms

Cited in

(3)

• Preclustering algorithms for imprecise points
• Approximation algorithms for clustering with dynamic points
• Bike rebalancing: how to find a balanced matching in the k center problem?

This page was built for publication: Approximation algorithms for clustering with dynamic points

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