Clustering through continuous facility location problems

DOI10.1016/J.TCS.2016.10.001zbMath1357.90082OpenAlexW2533751695MaRDI QIDQ346248

Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Luis A. A. Meira

Publication date: 5 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.10.001

zbMATH Keywords

approximation algorithms\(k\)-clusteringapproximate center setscontinuous facility location problemrandom sampling procedure

Mathematics Subject Classification ID

Continuous location (90B85) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (3)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ New variants of the simple plant location problem and applications ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• On approximate geometric \(k\)-clustering
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Linear-time approximation schemes for clustering problems in any dimensions
• A new greedy approach for facility location problems
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• On k-Median clustering in high dimensions
• A PTAS for k-means clustering based on weak coresets
• The Planar k-Means Problem is NP-Hard
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• A local search approximation algorithm for k-means clustering
• Least squares quantization in PCM
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Smaller coresets for k-median and k-means clustering
• (1 + ε)-Approximation for Facility Location in Data Streams

This page was built for publication: Clustering through continuous facility location problems