A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization

DOI10.1016/0166-218X(94)00016-7zbMATH Open0839.90086MaRDI QIDQ1897348FDOQ1897348

Authors Ross Baldick 

Publication date 23 June 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hardnesspolynomially solvable integer quadratic optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• Convex separable optimization is not much harder than linear optimization
• Reduction of nonlinear integer separable programming problems^∗
• Subdeterminants and concave integer quadratic programming
• A branch and bound algorithm for solving separable convex integer programming problems
• Separable standard quadratic optimization problems

Cites work

• scientific article; zbMATH DE number 51266 (Why is no real title available?)
• scientific article; zbMATH DE number 3479762 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 194432 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• scientific article; zbMATH DE number 3335677 (Why is no real title available?)
• A Graph-Theoretic Equivalence for Integer Programs
• A polynomial algorithm for an integer quadratic non-separable transportation problem
• A solvable case of quadratic 0-1 programming
• Convex separable optimization is not much harder than linear optimization
• Degree-two Inequalities, Clique Facets, and Biperfect Graphs
• Generalization of Barahona's algorithm for cases of integer non-linear programming with box constraints
• Geometric algorithms and combinatorial optimization
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Minimum cuts and related problems
• Modular Constructions for Combinatorial Geometries
• On polynomial solvability of the high multiplicity total weighted tardiness problem
• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• Selected Applications of Minimum Cuts in Networks
• Some proximity and sensitivity results in quadratic integer programming
• Unimodular functions

Cited in

(7)

• Tensors in computations
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• Complexity and algorithms for nonlinear optimization problems
• Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• Quadratic M-convex and L-convex functions
• Convex separable optimization is not much harder than linear optimization

This page was built for publication: A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization

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