A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
From MaRDI portal
Publication:414887
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
convex programming; satisfiability; constraint satisfaction; polynomial space; exponential-time algorithm; measure and conquer; hybrid instances
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Breaking Cycle Structure to Improve Lower Bound for Max-SAT, Faster graph coloring in polynomial space, 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
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