Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds

DOI10.1137/15M1053369zbMath1372.68305MaRDI QIDQ5269825

David P. Williamson, Matthias Poloczek, Anke van Zuylen, Georg Schnitger

Publication date: 28 June 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsrandomized algorithmsgreedy algorithmsmaximum satisfiability problempriority algorithms

Mathematics Subject Classification ID

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

Related Items (16)

A novel algorithm for Max Sat calling MOCE to order ⋮ An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Advice complexity of adaptive priority algorithms ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ Advice complexity of priority algorithms ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ A refined branching algorithm for the maximum satisfiability problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a model for backtracking and dynamic programming
• Models of greedy algorithms for graph problems
• Simplified tight analysis of Johnson's algorithm
• Randomized priority algorithms
• Priority algorithms for graph optimization problems
• Approximation algorithms for combinatorial problems
• Tight bound on Johnson's algorithm for maximum satisfiability
• (Incremental) priority algorithms
• Simpler 3/4-Approximation Algorithms for MAX SAT
• The Design of Approximation Algorithms
• Towards Sharp Inapproximability for Any 2-CSP
• Bounds on Greedy Algorithms for MAX SAT
• Submodular Max-SAT
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Probability Inequalities for Sums of Bounded Random Variables
• On Some Recent Approximation Algorithms for MAX SAT
• Some optimal inapproximability results
• Approximation and Online Algorithms

This page was built for publication: Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds