A solvable case of quadratic 0-1 programming
The problem of minimizing a quadratic function \(f(x)=x^ tQx+cx\) with symmetric matrix Q and Boolean x is considered. Finding the minimum of f(x) is equivalent to finding an assignment of values to the variables \(s_ i\) \((s_ i=2x_ i-1\), \(s_ i\in \{-1,1\})\) that maximizes \(\sum \{w_{ij}:\) \(s_ i=-s_ i\}\) where \(w_{ij}=(1/4)q_{ij}\) for \(1\leq i\leq j\leq n\) and \(w_{0j}=c_ j+\sum^{n}_{i=j}q_{ji}\) for \(0\leq j\leq n\). This is equivalent to finding a maximum weighted cut in the graph \(H=(U,F)\), where \(U=\{0,1,...,n\}\), and \(ij\in F\Leftrightarrow w_{ij}\neq 0\). The case when the graph \(H=(U,F)\) has a vertex u such that \(H\setminus u\) is series-parallel is considered. In this case an algorithm having computing time 0(n) is proposed.
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Methods of Nonlinear 0-1 Programming
- Minimum cuts and related problems
- On certain polytopes associated with graphs
- Polytope des independants d'un graphe série-parallèle
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- The indefinite zero-one quadratic problem
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Topology of series-parallel networks
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Experiments in quadratic 0-1 programming
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- A solvable class of quadratic 0-1 programming
- An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree
- Simulated annealing for the unconstrained quadratic pseudo-Boolean function
- The generalized vertex cover problem and some variations
- Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
- Checking robust nonsingularity is NP-hard
- An evolutionary heuristic for quadratic 0-1 programming
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- On solving a non-convex quadratic programming problem involving resistance distances in graphs
- The basic algorithm for pseudo-Boolean programming revisited
- Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- 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 algorithms for nonlinear optimization problems
- A tight lower bound for a special case of quadratic 0-1 programming
- 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
- scientific article; zbMATH DE number 3848971 (Why is no real title available?)
- scientific article; zbMATH DE number 4070666 (Why is no real title available?)
- The unconstrained binary quadratic programming problem: a survey
- On Linear Recognition of Tree-Width at Most Four
- A polynomial case of convex integer quadratic programming problems with box integer constraints
- Complexity and polynomially solvable special cases of QUBO
- A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX
- Global equilibrium search applied to the unconstrained binary quadratic optimization problem
- A polynomial case of unconstrained zero-one quadratic optimization
- Efficient joint object matching via linear programming
- On the complexity of binary polynomial optimization over acyclic hypergraphs
- Adaptive randomization in network data
- Locating facilities which interact: Some solvable cases
- Pseudo-Boolean optimization
- Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
- Computational complexity of norm-maximization
This page was built for publication: A solvable case of quadratic 0-1 programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079494)
