Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ELLIPSOID METHOD:
Reports tagged with ellipsoid method:
TR07-037 | 2nd February 2007
Leonid Gurvits

#### Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Revisions: 1

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.
Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and
with better rates if the affine dimensions of most of the sets $K_i$ are small.\\
Our approach is ... more >>>

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