Lossy kernelization of same-size clustering

DOI10.1007/978-3-031-09574-0_7MaRDI QIDQ2097218zbMATH OpenOpenAlexFDO

Authors Sayan Bandyapadhyay, Fedor V. Fomin, Nidhi Purohit, Kirill Siminov, Petr A. Golovach

Publication date 11 November 2022

Full work available at URL https://arxiv.org/abs/2107.07383

zbMATH Keywords

k-median clusteringkernelizationlossy kernelsparameterized approximation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• A constant-factor approximation algorithm for the k-median problem
• A unified framework for approximating and clustering data
• A unified framework for clustering constrained data without locality property
• A unified framework of FPT approximation algorithms for clustering problems
• An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation
• Approximating k-median with non-uniform capacities
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Bi-factor approximation algorithms for hard capacitated k-median problems
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• Constrained Clustering
• Effectiveness of local search for geometric optimization
• Faster algorithms for the constrained k-means problem
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 6850339 (Why is no real title available?)
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Kernelization of packing problems
• Kernelization. Theory of parameterized preprocessing
• Linear-time approximation schemes for clustering problems in any dimensions
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernels for graph contraction problems
• On coresets for k-means and k-median clustering
• On the fixed-parameter tractability of capacitated clustering
• On the parameterized complexity of contraction to generalization of trees
• On Two Segmentation Problems
• On uniform capacitated k-median beyond the natural LP relaxation
• On variants of k-means clustering
• Parameterized algorithms
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Parameterized low-rank binary matrix approximation
• The hardness of approximation: Gap location
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering

Cited in

(3)

• Cluster differences scaling with a within-clusters loss component and a fuzzy successive approximation strategy to avoid local minima
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• From data completion to problems on hypercubes: a parameterized analysis of the independent set problem

This page was built for publication: Lossy kernelization of same-size clustering

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