Open questions in complexity theory for numerical optimization
From MaRDI portal
Publication:687097
DOI10.1007/BF01581088zbMath0784.90102MaRDI QIDQ687097
Stephen A. Vavasis, Panos M. Pardalos
Publication date: 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Related Items
Some geometric results in semidefinite programming, Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables, On the complexity of detecting convexity over a box, NP-hardness of deciding convexity of quartic polynomials and related problems, Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem, On cones of nonnegative quartic forms, A convex polynomial that is not sos-convex, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Complexity aspects of local minima and related notions, On the complexity of finding a local minimizer of a quadratic function over a polytope, Strongly polynomial algorithm for two special minimum concave cost network flow problems
Cites Work
- Approximation algorithms for indefinite quadratic programming
- Checking local optimality in constrained quadratic programming is NP- hard
- How easy is local search?
- Complexity of linear programming
- Quadratic programming with one negative eigenvalue is NP-hard
- On the solution of concave knapsack problems
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Linear Programming in Linear Time When the Dimension Is Fixed
- Some NP-complete problems in quadratic and nonlinear programming
- Computational complexity of complementary pivot methods
- A polynomial time solvable concave network flow problem
- Bimatrix Equilibrium Points and Mathematical Programming
