Grothendieck-type inequalities in combinatorial optimization

2011/08/11 by Khot, Subhash, Naor, Assaf
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA)

paper · doi:10.48550/arxiv.1108.2464

Abstract

We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity.

Related

• From Parseval to Grothendieck and a little beyond, part I
• An elementary and unified proof of Grothendieck's inequality
• On the Complexity of Combinatorial Optimization on Fixed Structures
• Inapproximability of Combinatorial Optimization Problems
• A sub-constant improvement in approximating the positive semidefinite Grothendieck problem