Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
From MaRDI portal
Publication:5269825
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
Cites work
- scientific article; zbMATH DE number 2086914 (Why is no real title available?)
- scientific article; zbMATH DE number 1833408 (Why is no real title available?)
- scientific article; zbMATH DE number 2119703 (Why is no real title available?)
- (Incremental) priority algorithms
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation algorithms for combinatorial problems
- Approximation and Online Algorithms
- Bounds on greedy algorithms for MAX SAT
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Models of greedy algorithms for graph problems
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- On Some Recent Approximation Algorithms for MAX SAT
- On the Approximation of Maximum Satisfiability
- Priority algorithms for graph optimization problems
- Probability Inequalities for Sums of Bounded Random Variables
- Randomized greedy: new variants of some classic approximation algorithms
- Randomized priority algorithms
- Randomized variants of Johnson's algorithm for MAX SAT
- Simpler 3/4-approximation algorithms for MAX SAT
- Simplified tight analysis of Johnson's algorithm
- Some optimal inapproximability results
- Submodular Max-SAT
- The design of approximation algorithms
- Tight bound on Johnson's algorithm for maximum satisfiability
- Toward a model for backtracking and dynamic programming
- Towards sharp inapproximability for any 2-CSP
Cited in
(22)- Revisiting maximum satisfiability and related problems in data streams
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Randomized greedy: new variants of some classic approximation algorithms
- Advice complexity of adaptive priority algorithms
- Bounds on greedy algorithms for MAX SAT
- Simpler 3/4-approximation algorithms for MAX SAT
- Optimizing over serial dictatorships
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Optimizing over serial dictatorships
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Revisiting maximum satisfiability and related problems in data streams
- Adapting local sequential algorithms to the distributed setting
- Simple approximation algorithms for balanced MAX~2SAT
- The best \(m\)-term approximation and greedy algorithms
- A refined branching algorithm for the maximum satisfiability problem
- On the greedy algorithm for satisfiability
- On extensions of the deterministic online model for bipartite matching and max-sat
- Randomized variants of Johnson's algorithm for MAX SAT
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- A novel algorithm for Max Sat calling MOCE to order
- 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)
