On the Approximation of Maximum Satisfiability
From MaRDI portal
Publication:4314502
DOI10.1006/jagm.1994.1045zbMath0820.68056OpenAlexW2001564241WikidataQ100330562 ScholiaQ100330562MaRDI QIDQ4314502
Publication date: 23 November 1994
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1994.1045
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
Simplified tight analysis of Johnson's algorithm ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ Unnamed Item ⋮ Partial Satisfaction of k-Satisfiable Formulas ⋮ 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 ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Max NP-completeness made easy ⋮ Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\) ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Pseudo-Boolean optimization ⋮ Maximum satisfiability: how good are tabu search and plateau moves in the worst-case? ⋮ A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Alphabet indexing for approximating features of symbols ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ Tight bound on Johnson's algorithm for maximum satisfiability ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Locally consistent constraint satisfaction problems ⋮ Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
