Characterization of QUBO reformulations for the maximum k-colorable subgraph problem

DOI10.1007/S11128-022-03421-ZMaRDI QIDQ2107015zbMATH OpenOpenAlexFDO

Authors Rodolfo Quintero, David E. Bernal, Luis Fernando Zuluaga, Tamás Terlaky

Publication date 29 November 2022

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.09462

zbMATH Keywords

Chimera versus Pegasus D-wave annealercombinatorial optimizationNISQ devicesquantum computingQUBO reformulations

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Combinatorial optimization (90C27)

Recommendations

• Penalty and partitioning techniques to improve performance of QUBO solvers
• Reformulating the harmonious colouring problem for quantum annealing
• Quantum solutions for densest \(k\)-subgraph problems
• QUBO formulations for the graph isomorphism problem and related problems
• Modeling the Costas array problem in QUBO for quantum annealing

Cites work

• A case study in programming a quantum annealer for hard operational planning problems
• A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
• A MAX-CUT formulation of 0/1 programs
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integer Programming
• Integer programming techniques for minor-embedding in quantum annealers
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• New bounds for the -k-cut and chromatic number of a graph
• On characterization of maximal independent sets via quadratic optimization
• On spectrum sharing games
• On the Shannon capacity of a graph
• Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
• Penalty and partitioning techniques to improve performance of QUBO solvers
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• QUBO formulations for the graph isomorphism problem and related problems
• Reducibility among combinatorial problems
• Relationship between minimum gap and success probability in adiabatic quantum computing
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Some news about the independence number of a graph
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• The approximation of maximum subgraph problems
• The Maximum k-Colorable Subgraph Problem and Related Problems
• The maximum k-colorable subgraph problem and orbitopes
• The maximum k-colorable subgraph problem for chordal graphs

Cited in

(8)

• Quantum solutions for densest \(k\)-subgraph problems
• QUBO formulations of the longest path problem
• Penalty and partitioning techniques to improve performance of QUBO solvers
• Reformulating the harmonious colouring problem for quantum annealing
• Solving the Kemeny ranking aggregation problem with quantum optimization algorithms
• The set partitioning problem in a quantum context
• Characterization of QUBO reformulations for the maximum k-colorable subgraph problem
• A copositive framework for analysis of hybrid Ising-classical algorithms

This page was built for publication: Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

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