Approximation algorithms for indefinite quadratic programming
From MaRDI portal
Publication:687094
DOI10.1007/BF01581085zbMath0845.90095MaRDI QIDQ687094
Publication date: 16 September 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, Global solutions to folded concave penalized nonconvex learning, Provable randomized rounding for minimum-similarity diversification, An efficient global algorithm for a class of indefinite separable quadratic programs, A trust-region strategy for minimization on arbitrary domains, Games of fixed rank: a hierarchy of bimatrix games, A FPTAS for a class of linear multiplicative problems, A reformulation-convexification approach for solving nonconvex quadratic programming problems, Trading performance for stability in Markov decision processes, The complexity of approximating a nonlinear program, A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity, An FPTAS for optimizing a class of low-rank functions over a polytope, Approximation algorithm for a class of global optimization problems, An FPTAS for minimizing the product of two non-negative linear cost functions, Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution, New formulations of the multiple sequence alignment problem, An approximation algorithm for indefinite mixed integer quadratic programming, An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints, On mutual concavity and strategically-zero-sum bimatrix games, A better differential approximation ratio for symmetric TSP, Complexity bounds for second-order optimality in unconstrained optimization, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Approximation algorithms for indefinite quadratic programming, Open questions in complexity theory for numerical optimization, Linear decomposition approach for a class of nonconvex programming problems, A continuous approch for globally solving linearly constrained quadratic, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Quadratic programming and combinatorial minimum weight product problems, A new algorithm for the general quadratic programming problems with box constraints, Separable and low-rank continuous games, Subdeterminants and Concave Integer Quadratic Programming, On approximation algorithms for concave mixed-integer quadratic programming, Differential approximation of NP-hard problems with equal size feasible solutions, Complexity results for some global optimization problems, Differential approximation algorithms for some combinatorial optimization problems, Optimization of a convex program with a polynomial perturbation, Differential approximation results for the traveling salesman problem with distances 1 and 2
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the upper envelope of n line segments in O(n log n) time
- Approximation algorithms for indefinite quadratic programming
- An O(n) algorithm for quadratic knapsack problems
- Constrained global optimization: algorithms and applications
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- Quadratic programming with one negative eigenvalue is NP-hard
- Local minima for indefinite quadratic knapsack problems
- On the solution of concave knapsack problems
- Quadratic programming is in NP
- A lagrangean relaxation algorithm for the constrained matrix problem
- Some NP-complete problems in quadratic and nonlinear programming
- A polynomially bounded algorithm for a singly constrained quadratic program
