An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem

DOI10.1145/3064174MaRDI QIDQ4577945zbMATH OpenOpenAlexFDO

Authors Matthias Poloczek, David P. Williamson

Publication date 6 August 2018

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3064174

zbMATH Keywords

local searchgreedy algorithmsmaximum satisfiabilitycomplete solvers

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 1302170
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• scientific article; zbMATH DE number 1552232
• On Some Recent Approximation Algorithms for MAX SAT

Cites work

• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• scientific article; zbMATH DE number 956864 (Why is no real title available?)
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Approximation algorithms for combinatorial problems
• Bounds on greedy algorithms for MAX SAT
• CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Cores in core based MaxSat algorithms: an analysis
• Deterministic algorithms for submodular maximization problems
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Iterative and core-guided maxsat solving: a survey and assessment
• Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
• Multi-criteria optimization in answer set programming
• New local search methods for partial MaxSAT
• On Some Recent Approximation Algorithms for MAX SAT
• On Syntactic versus Computational Views of Approximability
• On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem
• On using incremental encodings in unsatisfiability-based MaxSAT solving
• Open-WBO: a modular MaxSAT solver
• Progress in clasp series 3
• Randomized greedy: new variants of some classic approximation algorithms
• Randomized variants of Johnson's algorithm for MAX SAT
• Simpler 3/4-approximation algorithms for MAX SAT
• Tight bound on Johnson's algorithm for maximum satisfiability
• Unsatisfiability-based optimization in clasp
• \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver

Cited in

(1)

• On extensions of the deterministic online model for bipartite matching and max-sat

This page was built for publication: An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem

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