ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-009 | 28th November 2011 12:18

Computational Complexity, NP Completeness and Optimization Duality: A Survey

RSS-Feed




TR12-009
Authors: Prabhu Manyem, Julien Ugon
Publication: 3rd February 2012 08:40
Downloads: 1680
Keywords: 


Abstract:

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 at a similar phenomenon in finite
model theory relating to complexity and optimization.



ISSN 1433-8092 | Imprint