scientific article; zbMATH DE number 1302170

zbMATH Open0926.90079MaRDI QIDQ4247437FDOQ4247437

Authors: Roberto Battiti, Marco Protasi 

Publication date: 11 November 1999

Title of this publication is not available (Why is that?)

Recommendations

• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1002206
• Algorithms for the maximum satisfiability problem
• Improved approximation algorithms for MAX SAT

zbMATH Keywords

approximation algorithmlocal searchSATsatisfiability problemmaximum satisfiability

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (25)

• Sums of squares based approximation algorithms for MAX-SAT
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• On the hardness of approximating max-satisfy
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Title not available (Why is that?)
• On exact selection of minimally unsatisfiable subformulae
• Worst-case study of local search for MAX-\(k\)-SAT.
• Differential approximation of MIN SAT, MAX SAT and related problems
• On Approximation Algorithms for Hierarchical MAX-SAT
• Title not available (Why is that?)
• On Some Recent Approximation Algorithms for MAX SAT
• Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Restoring satisfiability or maintaining unsatisfiability by finding small unsatisfiable subformulae
• A nonmonotone GRASP
• Solving weighted MAX-SAT via global equilibrium search
• Approximating minimal unsatisfiable subformulae by means of adaptive core search
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
• Theory and Applications of Satisfiability Testing
• Practical applications of the alternating cycle decomposition
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Improved exact algorithms for MAX-SAT
• Algorithms for the maximum satisfiability problem

Uses Software

• DIMACS

This page was built for publication:

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