  We provide a primal-dual framework for randomized approximation algorithms
utilizing semidefinite programming (SDP) relaxations. Our framework pairs a
continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and
more generally, Max-Boolean Constraint Satisfaction and MaxQ (maximization of a
positive semidefinite quadratic form over the hypercube) with new APX-complete
problems which are stated as convex optimization problems with exponentially
many variables. These new dual counterparts, based on what we call Grothendieck
covers, range from fractional cut covering problems (for MaxCut) to tensor sign
covering problems (for MaxQ). For each of these problem pairs, our framework
transforms the randomized approximation algorithms with the best known
approximation factors for the primal problems to randomized approximation
algorithms for their dual counterparts with reciprocal approximation factors
which are tight with respect to the Unique Games Conjecture. For each
APX-complete pair, our algorithms solve a single SDP relaxation and generate
feasible solutions for both problems which also provide approximate optimality
certificates for each other. Our work utilizes techniques from areas of
randomized approximation algorithms, convex optimization, spectral
sparsification, as well as Chernoff-type concentration results for random
matrices.
