Approximate Kernel Clustering

DOI10.1112/S002557930000098XzbMath1195.68114arXiv0807.4626OpenAlexW2567976503MaRDI QIDQ3400770

Subhash A. Khot, Assaf Naor

Publication date: 5 February 2010

Published in: Mathematika (Search for Journal in Brave)

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

zbMATH Keywords

clusteringpolynomial-time approximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Standard simplices and pluralities are not the most noise stable ⋮ Solution of the propeller conjecture in \(\mathbb R^3\) ⋮ Unnamed Item ⋮ UG-hardness to NP-hardness by losing half

Cites Work

• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Limit theorems for polylinear forms
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• A proof of the Grothendieck inequality
• On maximization of quadratic form over intersection of ellipsoids with common center
• Near-optimal algorithms for unique games
• Semidefinite relaxation and nonconvex quadratic optimization
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximating the Cut-Norm via Grothendieck's Inequality
• Quadratic forms on graphs

This page was built for publication: Approximate Kernel Clustering