Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
DOI10.1137/15M1053369zbMATH Open1372.68305MaRDI QIDQ5269825FDOQ5269825
Authors: Matthias Poloczek, David P. Williamson, Anke van Zuylen, Georg Schnitger 
Publication date: 28 June 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Bounds on greedy algorithms for MAX SAT
- scientific article; zbMATH DE number 1002206
- Approximation algorithms for the maximum satisfiability problem
- On the greedy algorithm for satisfiability
- scientific article; zbMATH DE number 1258327
- scientific article; zbMATH DE number 1302170
- scientific article; zbMATH DE number 1552232
- On Some Recent Approximation Algorithms for MAX SAT
- Algorithms for the maximum satisfiability problem
randomized algorithmsapproximation algorithmsgreedy algorithmsmaximum satisfiability problempriority algorithms
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- The design of approximation algorithms
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- Some optimal inapproximability results
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation and Online Algorithms
- Title not available (Why is that?)
- On the Approximation of Maximum Satisfiability
- Towards sharp inapproximability for any 2-CSP
- (Incremental) priority algorithms
- Toward a model for backtracking and dynamic programming
- On Some Recent Approximation Algorithms for MAX SAT
- Priority algorithms for graph optimization problems
- Tight bound on Johnson's algorithm for maximum satisfiability
- Bounds on Greedy Algorithms for MAX SAT
- Models of greedy algorithms for graph problems
- Randomized priority algorithms
- Title not available (Why is that?)
- Simplified tight analysis of Johnson's algorithm
- Simpler 3/4-Approximation Algorithms for MAX SAT
- Submodular Max-SAT
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (20)
- A refined branching algorithm for the maximum satisfiability problem
- On extensions of the deterministic online model for bipartite matching and max-sat
- Simple approximation algorithms for balanced MAX~2SAT
- The best \(m\)-term approximation and greedy algorithms
- A novel algorithm for Max Sat calling MOCE to order
- Advice complexity of adaptive priority algorithms
- On the greedy algorithm for satisfiability
- Revisiting maximum satisfiability and related problems in data streams
- Advice complexity of priority algorithms
- Optimizing over serial dictatorships
- Title not available (Why is that?)
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Revisiting maximum satisfiability and related problems in data streams
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- Optimizing over serial dictatorships
- On conceptually simple algorithms for variants of online bipartite matching
- Using the method of conditional expectations to supply an improved starting point for CCLS
This page was built for publication: Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5269825)
