Constant-factor approximation algorithms for some maximin multi-clustering problems

DOI10.1007/978-3-031-35305-5_6zbMATH Open1528.90279OpenAlexW4381956509MaRDI QIDQ6134049FDOQ6134049

Vladimir Khandeev, Sergey Neshchadim

Publication date: 21 August 2023

Published in: Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-35305-5_6

zbMATH Keywords

clusteringapproximation algorithmmax-min problemNP-hardnessEuclidean spacebounded scatter

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Approximation algorithms (68W25)

Cites Work

• NP-hardness of Euclidean sum-of-squares clustering
• Outlier Analysis
• Algorithms for facility location problems with outliers. (Extended abstract)
• Clustering to minimize the maximum intercluster distance
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• Approximation algorithms for geometric median problems
• On the complexity of some quadratic Euclidean partition problems into balanced clusters
• Max-Min Problems of Searching for Two Disjoint Subsets

Cited In (4)

• An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes
• On the complexity of the problem of choice of large clusters
• Title not available (Why is that?)
• A constant factor approximation algorithm for a class of classification problems

This page was built for publication: Constant-factor approximation algorithms for some maximin multi-clustering problems

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