Bypassing UGC from some optimal geometric inapproximability results

DOI10.1145/2737729zbMATH Open1398.68194OpenAlexW2397159611MaRDI QIDQ4962201FDOQ4962201

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

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?

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)

Cited In (11)

• Title not available (Why is that?)
• A greedy algorithm for subspace approximation problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)