Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial

DOI10.1007/BF00253808zbMath0770.90048MaRDI QIDQ1203065

Yasutoshi Yajima, Takahito Kuno, Hiroshi Konno

Publication date: 4 February 1993

Published in: Computational Optimization and Applications (Search for Journal in Brave)

zbMATH Keywords

global optimizationprobabilistic analysisaverage number of stepsbilinear-programmingparametric simplex algorithms

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Theoretical and computational results about optimality-based domain reductions, The Bipartite QUBO, A FPTAS for a class of linear multiplicative problems, An outcome-space finite algorithm for solving linear multiplicative programming, The bipartite quadratic assignment problem and extensions, Data separation via a finite number of discriminant functions: a global optimization approach, Multiplicative programming problems: Analysis and efficient point search heuristic, A branch-and-reduce approach to global optimization, A global optimization approach for solving generalized nonlinear multiplicative programming problem, Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis, Robust metaheuristic algorithm for redundancy optimization in large-scale complex systems, A nonisolated optimal solution of general linear multiplicative programming problems, \(NP\)-hardness of linear multiplicative programming and related problems, The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global optimization algorithms for linearly constrained indefinite quadratic problems
• Quadratic programming with one negative eigenvalue is NP-hard
• Parametric simplex algorithms for solving a special class of nonconvex minimization problems
• Efficient algorithms for solving rank two and rank three bilinear programming problems
• Quadratic programming is in NP
• On the average number of steps of the simplex method of linear programming
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• The Efficiency of the Simplex Method: A Survey
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• Computational complexity of parametric linear programming
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• On the expected number of linear complementarity cones intersected by random and semi-random rays
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems