Clustering affine subspaces: hardness and algorithms

DOI10.1137/1.9781611973105.58MaRDI QIDQ5741766zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Leonard J. Schulman

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.58

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Linear-time approximation scheme for k-means clustering of axis-parallel affine subspaces
• Analysis of incomplete data and an intrinsic-dimension Helly theorem
• Analysis of incomplete data and an intrinsic-dimension Helly theorem
• Clustering lines in high-dimensional space, classification of incomplete data
• Algorithms and hardness for subspace approximation

Cited in

(10)

• The complexity of binary matrix completion under diameter constraints
• On the parameterized complexity of clustering problems for incomplete data
• Clustering, Hamming Embedding, Generalized LSH and the Max Norm
• Clustering lines in high-dimensional space, classification of incomplete data
• How to Round Subspaces: A New Spectral Clustering Algorithm
• Analysis of incomplete data and an intrinsic-dimension Helly theorem
• Linear-time approximation scheme for k-means clustering of axis-parallel affine subspaces
• Improved separated red-blue center clustering
• Coresets for k-median of lines with group fairness constraints
• Matrix completion: approximating the minimum diameter

This page was built for publication: Clustering affine subspaces: hardness and algorithms

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