Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT

DOI10.1016/S0166-218X(00)00263-8zbMath0964.90041MaRDI QIDQ1841891

Joost P. Warners, Hans van Maaren

Publication date: 18 February 2001

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

zbMATH Keywords

combinatorial optimizationapproximate solutionapproximation algorithmsMAX CUTbinary convex quadratic optimizationMAX 2SAT

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Solving satisfiability problems using elliptic approximations -- effective branching rules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time transformation of linear inequalities into conjunctive normal form
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• On duality for Boolean programming
• An interior point algorithm to solve computationally difficult set covering problems
• On affine scaling algorithms for nonconvex quadratic programming
• Approximation algorithms for combinatorial problems
• Some simplified NP-complete graph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Laplacian eigenvalues and the maximum cut problem
• Solving the max-cut problem using eigenvalues
• Elliptic approximations of propositional formulae
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An Interior-Point Method for Semidefinite Programming