Clustering through continuous facility location problems

DOI10.1016/J.TCS.2016.10.001MaRDI QIDQ346248zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Local search approximation algorithms for the sum of squares facility location problems
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A constant-factor approximation algorithm for the \(k\)-median problem
• Approximation schemes for clustering problems

Cites work

• scientific article; zbMATH DE number 5764820 (Why is no real title available?)
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A PTAS for k-means clustering based on weak coresets
• A local search approximation algorithm for \(k\)-means clustering
• A new greedy approach for facility location problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximate clustering via core-sets
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation schemes for clustering problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Least squares quantization in PCM
• Linear-time approximation schemes for clustering problems in any dimensions
• On k-Median clustering in high dimensions
• On approximate geometric \(k\)-clustering
• On coresets for k-means and k-median clustering
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• The Planar k-Means Problem is NP-Hard
• The hardness of approximation of Euclidean \(k\)-means
• \((1 + \varepsilon)\)-approximation for facility location in data streams

Cited in

(7)

• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• Continuous facility location on graphs
• Using clustering analysis in a capacitated location-routing problem
• A clustering approach to the planar hub location problem
• New variants of the simple plant location problem and applications
• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• Local search approximation algorithms for the sum of squares facility location problems

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

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