Complexity and polynomially solvable special cases of QUBO
From MaRDI portal
Recommendations
- The bipartite QUBO
- Introduction to QUBO
- The quadratic unconstrained binary optimization problem. Theory, algorithms, and applications
- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
- Applications and computational advances for solving the QUBO model
Cites work
- A New Algorithm for Generating All the Maximal Independent Sets
- A new polynomially solvable class of quadratic optimization problems with box constraints
- A partial k-arboretum of graphs with bounded treewidth
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- A polynomial case of unconstrained zero-one quadratic optimization
- A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
- A Separator Theorem for Planar Graphs
- A solvable case of quadratic 0-1 programming
- A solvable class of quadratic 0-1 programming
- A survey for the quadratic assignment problem
- A tribute to Frank Harary (in honor of his 70th birthday)
- Algorithms - ESA 2003
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Algorithms for minclique scheduling problems
- An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
- An improved fixed-parameter algorithm for max-cut parameterized by crossing number
- Assignment Problems
- Assignment Problems and the Location of Economic Activities
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Computing independent sets in graphs with large girth
- Decomposition by clique separators
- Diameter and treewidth in minor-closed graph families
- Easy and difficult objective functions for max cut
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- Geometric algorithms and combinatorial optimization
- Graph separation techniques for quadratic zero-one programming
- scientific article; zbMATH DE number 6118217 (Why is no real title available?)
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 4200260 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2079399 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Maximizing the Product of Two Linear Functions In 0-1 Variables
- Maximum cut on line and total graphs
- Maximum cut parameterized by crossing number
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- Maximum weight independent sets in hole- and dart-free graphs
- Minimization of half-products
- Minimum cuts and related problems
- Multi-Terminal Network Flows
- Nested Dissection of a Regular Finite Element Mesh
- New results on the completion time variance minimization
- Node-and edge-deletion NP-complete problems
- NP-hardness of the Euclidean Max-Cut problem
- Numerical linear algebra and matrix factorizations
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- On duality gap in binary quadratic programming
- On the complexity of integer programming
- On the practically interesting instances of MAXCUT
- Optimal cuts in graphs and statistical mechanics
- Optimization via enumeration: A new algorithm for the max cut problem
- Optimization, approximation, and complexity classes
- Partitioning planar graphs: a fast combinatorial approach for max-cut
- Polynomially solvable cases of binary quadratic programs
- Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
- Selected Applications of Minimum Cuts in Networks
- Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
- Solving the weighted stable set problem in claw-free graphs via decomposition
- Some simplified NP-complete graph problems
- Space bounds for a game on graphs
- Tape bounds for time-bounded Turing machines
- The basic algorithm for pseudo-Boolean programming revisited
- The clique problem in ray intersection graphs
- The generalized vertex cover problem and some variations
- The max clique problem in classes of string-graphs
- The max-cut problem on graphs not contractible to \(K_ 5\)
- The maximum clique problem
- The maximum clique problem in multiple interval graphs
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- The quadratic assignment problem. Theory and algorithms
- The unconstrained binary quadratic programming problem: a survey
- The Wiener maximum quadratic assignment problem
- Unifying maximum cut and minimum cut of a planar graph
- Unit disk graphs
- Weakly bipartite graphs and the max-cut problem
- Well-solvable cases of the QAP with block-structured matrices
Cited in
(12)- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
- Polynomial degree vs. quantum query complexity
- scientific article; zbMATH DE number 205727 (Why is no real title available?)
- Introduction to QUBO
- Applications and computational advances for solving the QUBO model
- The random QUBO
- Fast heuristics and approximation algorithms
- The bipartite QUBO
- QUBO software
- The quadratic unconstrained binary optimization problem. Theory, algorithms, and applications
- The rotation distance of brooms
- QUBO formulation for aircraft load optimization
This page was built for publication: Complexity and polynomially solvable special cases of QUBO
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5050143)
