Bypassing UGC from some optimal geometric inapproximability results

DOI10.1145/2737729MaRDI QIDQ4962201zbMATH OpenOpenAlexFDO

Authors Prasad Raghavendra, Rishi Saket, Yi Wu, Venkatesan Guruswami

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2737729

zbMATH Keywords

NP-hardnesssubspace approximationlabel cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 7053310
• Algorithms and hardness for subspace approximation
• The UGC hardness threshold of the \(l_p\) Grothendieck problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Cited in

(11)

• scientific article; zbMATH DE number 3974286 (Why is no real title available?)
• A greedy algorithm for subspace approximation problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• Grothendieck-type inequalities in combinatorial optimization
• The UGC hardness threshold of the \(l_p\) Grothendieck problem
• The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins
• scientific article; zbMATH DE number 7525465 (Why is no real title available?)
• Algorithms and hardness for subspace approximation
• The quest for strong inapproximability results with perfect completeness
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms

This page was built for publication: Bypassing UGC from some optimal geometric inapproximability results

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