A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between

DOI10.1016/j.jcss.2011.05.010zbMath1238.68066OpenAlexW2895952552MaRDI QIDQ414887

Gregory B. Sorkin, Serge Gaspers

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.010

zbMATH Keywords

convex programmingsatisfiabilityconstraint satisfactionpolynomial spaceexponential-time algorithmmeasure and conquerhybrid instances

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (19)

A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A new upper bound for Max-2-SAT: A graph-theoretic approach ⋮ Exact algorithms for dominating set ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Breaking Cycle Structure to Improve Lower Bound for Max-SAT ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Faster graph coloring in polynomial space ⋮ On the Number of Minimal Separators in Graphs ⋮ $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Optimal 2-constraint satisfaction via sum-product algorithms
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New methods for 3-SAT decision and worst-case analysis
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A measure & conquer approach for the analysis of exact algorithms
• New Bounds for MAX-SAT by Clause Learning
• A new approach to proving upper bounds for MAX-2-SAT
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• New Upper Bounds for Maximum Satisfiability
• 3-coloring in time
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Feedback Vertex Set in Mixed Graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between