The Computational Complexity of Duality
DOI10.1137/16M105887XzbMath1353.65144arXiv1601.07629OpenAlexW2963251533MaRDI QIDQ2832893
Lek-Heng Lim, Shmuel Friedland
Publication date: 15 November 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.07629
approximationNP-hardproper conedual normdual coneMahler volumesymmetric convex bodyFenchel dualnorm ballpolynomial-time reducibleweak membership
Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Optimality conditions and duality in mathematical programming (90C46) Convex functions and convex programs in convex geometry (52A41) Positive matrices and their generalizations; cones of matrices (15B48) Numerical computation of matrix norms, conditioning, scaling (65F35) Complexity and performance of numerical algorithms (65Y20)
Related Items (9)
Cites Work
- On the computational complexity of membership problems for the completely positive cone and its dual
- On cones of nonnegative quartic forms
- Semidefinite representation of convex sets
- Geometric algorithms and combinatorial optimization.
- New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
- The concept of duality in convex analysis, and the characterization of the Legendre transform
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Some NP-complete problems in quadratic and nonlinear programming
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Most Tensor Problems Are NP-Hard
- Convex Analysis
This page was built for publication: The Computational Complexity of Duality