Open questions in complexity theory for numerical optimization

DOI10.1007/BF01581088MaRDI QIDQ687097zbMATH OpenFDO

Authors Panos M. Pardalos, Stephen A. Vavasis

Publication date 1992

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A polynomial time solvable concave network flow problem
• Approximation algorithms for indefinite quadratic programming
• Bimatrix Equilibrium Points and Mathematical Programming
• Checking local optimality in constrained quadratic programming is NP- hard
• Complexity of linear programming
• Computational complexity of complementary pivot methods
• How easy is local search?
• Linear Programming in Linear Time When the Dimension Is Fixed
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• On the solution of concave knapsack problems
• Quadratic programming with one negative eigenvalue is NP-hard
• Some NP-complete problems in quadratic and nonlinear programming

Cited in

(14)

• Open problems around exact algorithms
• On the complexity of detecting convexity over a box
• NP-hardness of deciding convexity of quartic polynomials and related problems
• Some geometric results in semidefinite programming
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• A convex polynomial that is not sos-convex
• scientific article; zbMATH DE number 501506 (Why is no real title available?)
• Complexity aspects of local minima and related notions
• The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
• Strongly polynomial algorithm for two special minimum concave cost network flow problems
• Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
• On cones of nonnegative quartic forms
• 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

This page was built for publication: Open questions in complexity theory for numerical optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687097)