A solvable case of quadratic 0-1 programming

DOI10.1016/0166-218X(86)90065-XzbMath0597.90059OpenAlexW1973069886MaRDI QIDQ1079494

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90065-x

zbMATH Keywords

max-cut problem series-parallel maximum weighted cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Quadratic programming (90C20) Boolean programming (90C09)

Related Items

Generalization of Barahona's algorithm for cases of integer non-linear programming with box constraints, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Complexity and Polynomially Solvable Special Cases of QUBO, A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX, A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization, Graph separation techniques for quadratic zero-one programming, The equipartition polytope. I: Formulations, dimension and basic facets, Computational aspects of a branch and bound algorithm for quadratic zero- one programming, The Boolean quadratic polytope: Some characteristics, facets and relatives, Experiments in quadratic 0-1 programming, Efficient joint object matching via linear programming, The unconstrained binary quadratic programming problem: a survey, On the complexity of binary polynomial optimization over acyclic hypergraphs, Adaptive randomization in network data, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, A polynomial case of convex integer quadratic programming problems with box integer constraints, A solvable class of quadratic 0-1 programming, Locating facilities which interact: Some solvable cases, The generalized vertex cover problem and some variations, Complexity and algorithms for nonlinear optimization problems, An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree, Pseudo-Boolean optimization, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, The basic algorithm for pseudo-Boolean programming revisited, Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Checking robust nonsingularity is NP-hard, An evolutionary heuristic for quadratic 0-1 programming, Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture, Computational complexity of norm-maximization, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem

Cites Work