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

DOI10.1016/J.AMC.2009.06.043zbMATH Open1179.90234OpenAlexW1987470888MaRDI QIDQ734870FDOQ734870

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

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

zbMATH Keywords

artificial intelligencesatisfiabilitytabu searchbranch-and-boundMax-SAT

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• 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
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• Improving exact algorithms for MAX-2-SAT
• A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Title not available (Why is that?)
• 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

Uses Software

• MaxSolver
• MAX-2-SAT

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)