Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds (Q5269825): Difference between revisions

Latest revision as of 00:37, 14 July 2024

scientific article; zbMATH DE number 6736410

Language	Label	Description	Also known as
English	Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds	scientific article; zbMATH DE number 6736410

Statements

instance of

scholarly article

0 references

title

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

0 references

0 references

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

28 June 2017

0 references

zbMATH Keywords

approximation algorithms

0 references

greedy algorithms

0 references

maximum satisfiability problem

0 references

priority algorithms

0 references

randomized algorithms

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Toward a model for backtracking and dynamic programming

0 references

Randomized priority algorithms

0 references

Towards Sharp Inapproximability for Any 2-CSP

0 references

Approximation and Online Algorithms

0 references

Submodular Max-SAT

0 references

Priority algorithms for graph optimization problems

0 references

(Incremental) priority algorithms

0 references

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

0 references

Approximate Constraint Satisfaction Requires Large LP Relaxations

0 references

Tight bound on Johnson's algorithm for maximum satisfiability

0 references

Q5365069

0 references

Models of greedy algorithms for graph problems

0 references

Simplified tight analysis of Johnson's algorithm

0 references

New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

0 references

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

0 references

Some optimal inapproximability results

0 references

Probability Inequalities for Sums of Bounded Random Variables

0 references

Approximation algorithms for combinatorial problems

0 references

Q4737518

0 references

Q4780789

0 references

Bounds on Greedy Algorithms for MAX SAT

0 references

Q5365070

0 references

On Some Recent Approximation Algorithms for MAX SAT

0 references

Simpler 3/4-Approximation Algorithms for MAX SAT

0 references

The Design of Approximation Algorithms

0 references

On the Approximation of Maximum Satisfiability

0 references

Q4828974

0 references

Identifiers

zbMATH Open document ID

1372.68305

0 references

DOI

10.1137/15M1053369

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5269825

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