Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Duality gap:
TR12-009 | 28th November 2011
Prabhu Manyem, Julien Ugon

Computational Complexity, NP Completeness and Optimization Duality: A Survey

We survey research that studies the connection between the computational complexity
of optimization problems on the one hand, and the duality gap between the primal and
dual optimization problems on the other. To our knowledge, this is the first survey that
connects the two very important areas. We further look ... more >>>

ISSN 1433-8092 | Imprint