Lossy kernelization of same-size clustering

DOI10.1007/S00224-023-10129-9MaRDI QIDQ6174654zbMATH OpenFDO

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

Publication date 17 August 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-023-10129-9

zbMATH Keywords

kernelizationparameterized approximation\(k\)-median clusteringlossy kernels

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites work

• 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?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• 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 Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
• Approximating k-median via pseudo-approximation
• Approximating k-median with non-uniform capacities
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Bi-factor approximation algorithms for hard capacitated k-median problems
• Computational intelligence paradigms. Innovative applications
• 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
• Kernelization of packing problems
• Kernelization. Theory of parameterized preprocessing
• Linear-time approximation schemes for clustering problems in any dimensions
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernels for graph contraction problems
• Matching theory
• On Two Segmentation 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 uniform capacitated k-median beyond the natural LP relaxation
• 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 complexity of categorical clustering with size constraints
• 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
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

Cited in

(1)

• Cluster differences scaling with a within-clusters loss component and a fuzzy successive approximation strategy to avoid local minima

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 Q6174654)