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