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

DOI10.1016/j.jcss.2011.05.010zbMath1238.68066MaRDI 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 programming; satisfiability; constraint satisfaction; polynomial space; exponential-time algorithm; measure and conquer; hybrid instances

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Exact algorithms for dominating set, A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between, A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP, A new upper bound for Max-2-SAT: A graph-theoretic approach, A faster polynomial-space algorithm for Max 2-CSP, Solving sparse instances of Max SAT via width reduction and greedy restriction, Parameterized measure \& conquer for problems with no small kernels, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Inclusion/exclusion meets measure and conquer, Improved exact algorithms for mildly sparse instances of MAX SAT, New exact algorithms for the 2-constraint satisfaction problem, On the Number of Minimal Separators in Graphs, 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, $K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs, 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

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