Grothendieck‐Type Inequalities in Combinatorial Optimization

2012/04/25 by Subhash Khot, Assaf Naor · 1 citation
Engineering · Computer Science · Mathematics · #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Type (biology) #Inequality #Mathematics #Combinatorial optimization #Computer science #Mathematical optimization #Combinatorics #Biology #Mathematical analysis

paper · doi:10.1002/cpa.21398

openalex publication_date 2012/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Abstract We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity. © 2011 Wiley Periodicals, Inc.

Citations

• Constantes de Grothendieck et fonctions de type positif sur les sphères
• On maximization of quadratic form over intersection of ellipsoids with common center
• Random sampling and approximation of MAX-CSPs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• New Bell inequalities for the singlet state: Going beyond the Grothendieck bound
• Quadratic forms on graphs
• Optimization, approximation, and complexity classes
• Szemerédi’s Lemma for the Analyst
• Quick Approximation to Matrices and Applications
• The Algorithmic Aspects of the Regularity Lemma
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Unbounded Violation of Tripartite Bell Inequalities
• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
• Optimal algorithms and inapproximability results for every CSP?
• On the Unique Games Conjecture (Invited Survey)
• On the power of unique 2-prover 1-round games
• Relaxations of Quadratic Programs in Operator Theory and System Analysis
• Regularity Lemmas and Combinatorial Algorithms
• A proof of the Grothendieck inequality
• Maximizing Quadratic Programs: Extending Grothendieck's Inequality

Cited by

• Grothendieck inequality [wikipedia]