Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOW RANK APPROXIMATION:
Reports tagged with Low rank approximation:
TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

#### Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>

ISSN 1433-8092 | Imprint