A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

DOI10.1016/J.AMC.2009.06.043MaRDI QIDQ734870zbMATH OpenOpenAlexFDO

Authors Gintaras Palubeckis

Publication date 14 October 2009

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2009.06.043

zbMATH Keywords

artificial intelligencesatisfiabilitytabu searchbranch-and-boundMax-SAT

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Boolean programming (90C09)

Recommendations

• Exact algorithms for MAX-SAT
• Improving exact algorithms for MAX-2-SAT
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• New Upper Bounds for Maximum Satisfiability

Cites work

• scientific article; zbMATH DE number 1114003 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 1795723 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 956857 (Why is no real title available?)
• scientific article; zbMATH DE number 956866 (Why is no real title available?)
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• AI 2007: Advances in artificial intelligence. 20th Australian joint conference on artificial intelligence, Gold Coast, Australia, December 2--6, 2007. Proceedings
• An efficient solver for weighted Max-SAT
• Experimental and Efficient Algorithms
• Faster exact algorithms for hard problems: A parameterized point of view
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improving exact algorithms for MAX-2-SAT
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Iterated tabu search for the maximum diversity problem
• Iterated tabu search for the unconstrained binary quadratic optimization problem
• Local Consistency in Weighted CSPs and Inference in Max-SAT
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• New inference rules for Max-SAT
• On the Approximation of Maximum Satisfiability
• On the recursive largest first algorithm for graph colouring
• Semidefinite programming based approaches to the break minimization problem
• Solving Max-SAT as weighted CSP
• Tabu Search—Part I

Cited in

(12)

• A Spectral Method for MAX2SAT in the Planted Solution Model
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Improving exact algorithms for MAX-2-SAT
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• Iterative and core-guided maxsat solving: a survey and assessment
• Incomplete inference for graph problems
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• An improved exact algorithm for least-squares unidimensional scaling

Describes a project that uses

Uses Software

• MAX-2-SAT
• MaxSolver

This page was built for publication: A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

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