Bypassing UGC from Some Optimal Geometric Inapproximability Results

DOI10.1145/2737729zbMath1398.68194OpenAlexW2397159611MaRDI QIDQ4962201

Rishi Saket, Yi Wu, Prasad Raghavendra, 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

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

Related Items (6)

Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins ⋮ Unnamed Item ⋮ A Greedy Algorithm for Subspace Approximation Problem ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness

This page was built for publication: Bypassing UGC from Some Optimal Geometric Inapproximability Results