Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Introduction <s> This is the first book to fully address the study of approximation algorithms as a tool for coping with intractable problems. With chapters contributed by leading researchers in the field, this book introduces unifying techniques in the analysis of approximation algorithms. APPROXIMATION ALGORITHMS FOR NP-HARD PROBLEMS is intended for computer scientists and operations researchers interested in specific algorithm implementations, as well as design tools for algorithms. Among the techniques discussed: the use of linear programming, primal-dual techniques in worst-case analysis, semidefinite programming, computational geometry techniques, randomized algorithms, average-case analysis, probabilistically checkable proofs and inapproximability, and the Markov Chain Monte Carlo method. The text includes a variety of pedagogical features: definitions, exercises, open problems, glossary of problems, index, and notes on how best to use the book. <s> BIB001 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Introduction <s> Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations. ::: For several special cases of QQP, e.g., convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. ::: In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition XXT=I. For this problem we show that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem. <s> BIB002 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Introduction <s> Covering the basic techniques used in the latest research work, the author consolidates progress made so far, including some very recent and promising results, and conveys the beauty and excitement of work in the field. He gives clear, lucid explanations of key results and ideas, with intuitive proofs, and provides critical examples and numerous illustrations to help elucidate the algorithms. Many of the results presented have been simplified and new insights provided. Of interest to theoretical computer scientists, operations researchers, and discrete mathematicians. <s> BIB003 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Introduction <s> It is shown that a general Lagrangian duality theory for constrained extremum problems can be drawn from a separation scheme in the Image Space, namely in the space where the functions of the given problem run. <s> BIB004
In optimization problems, the duality gap is the difference between the optimal solution values of the primal problem and the dual problem. The relationship between the duality gap and the computational complexity of optimization problems has been implicitly studied for the last few decades. The connection between the two phenomena has been subtly acknowledged. The gap has been exploited to design good approximation algorithms for NP-hard optimization problems  BIB001 BIB003 . However, we have been unable to locate a single piece of literature that addresses this issue explicitly. This report is an attempt to bring a great deal of evidence together and specifically address this issue. Does the existence of polynomial time algorithms for the primal and the dual problems mean that the duality gap is zero? Conversely, does the existence of a duality gap imply that either the primal problem or the dual problem is (or both are) NP-hard? Is there an inherent connection between computational complexity and strong duality (that is, zero duality gap)? Vecten and Fasbender (independently) were the first to discover the optimization duality BIB004 . They observed this phenomenon in the Fermat-Torricelli problem: Given a triangle T 1 , find the equilateral triangle circumscribed outside T 1 with the maximum height. They showed that this maximum height H is equal to the minimum sum of the distances from the vertices to T 1 to the Torricelli point BIB002 . Thus, this problem enjoys strong duality. The apparent connection between the duality gap and computational complexity was considered more than thirty years ago. Linear Programming (LP) is a well known optimization problem. In the mid 1970s, before Khachiyan published his ellipsoid algorithm, LP was thought to be polynomially solvable, precisely because it obeys strong duality; that is, the duality gap is zero. For a good description of the ellipsoid algorithm, the reader is referred to the good book by Fang and Puthenpura  . Strong duality also places the decision version of Linear Programming in the class NP ∩ CoNP; see Lemma 9 below. We should stress that this is not a survey on Lagrangian duality or any other form of optimization duality. Rather, this is a survey on the connections and relationships between the computational complexity of optimization problems and duality.