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

DOI10.1016/0166-218X(94)00016-7MaRDI QIDQ1897348zbMATH OpenFDO

Authors Ross Baldick

Publication date 23 June 1996

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

Full work available at URL https://doi.org/10.1016/0166-218X(94)00016-7

zbMATH Keywords

NP-hardnesspolynomially solvable integer quadratic optimization

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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)

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

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)