New Upper Bounds for Maximum Satisfiability
From MaRDI portal
Publication:4500858
DOI10.1006/jagm.2000.1075zbMath0959.68049OpenAlexW2154474334MaRDI QIDQ4500858
Rolf Niedermeier, Peter Rossmanith
Publication date: 6 May 2001
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/385c20806ee166f3ba62205793c13b6e28f5b3f2
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (36)
Improved exact algorithms for MAX-SAT ⋮ A logical approach to efficient Max-SAT solving ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ A Max-SAT Inference-Based Pre-processing for Max-Clique ⋮ Boosting branch-and-bound MaxSAT solvers with clause learning ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ A tighter upper bound for random MAX \(2\)-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. ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Incomplete inference for graph problems ⋮ Computational protein design as an optimization problem ⋮ An efficient solver for weighted Max-SAT ⋮ Breaking Cycle Structure to Improve Lower Bound for Max-SAT ⋮ MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability ⋮ A note on the complexity of minimum dominating set ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ Exact Algorithms for MAX-SAT ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Parameterizing above or below guaranteed values ⋮ Understanding the power of Max-SAT resolution through up-resilience ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Resolution for Max-SAT ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver ⋮ An Empirical Study of MAX-2-SAT Phase Transitions ⋮ Iterative and core-guided maxsat solving: a survey and assessment ⋮ Improving exact algorithms for MAX-2-SAT ⋮ A refined branching algorithm for the maximum satisfiability problem
Uses Software
This page was built for publication: New Upper Bounds for Maximum Satisfiability
