New exact algorithms for the 2-constraint satisfaction problem

DOI10.1016/J.TCS.2014.01.010MaRDI QIDQ2437759zbMATHOpenAlexFDO

Authors Alexander Golovnev, Konstantin Kutzkov

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.01.010

zbMATH Keywords

constraint satisfactionmaximum satisfiabilityexact exponential time algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• Exact Max 2-Sat: Easier and Faster
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Optimal 2-constraint satisfaction via sum-product algorithms

Cites work

• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A new approach to proving upper bounds for MAX-2-SAT
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• A note on the complexity of the chromatic number problem
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• An exact algorithm for MAX-CUT in sparse graphs
• An exact exponential time algorithm for counting bipartite cliques
• Applications of a Planar Separator Theorem
• Balanced coloring of bipartite graphs
• Computing Partitions with Applications to the Knapsack Problem
• Exact Max 2-Sat: Easier and Faster
• Finding a Maximum Independent Set
• Improved exact algorithms for MAX-SAT
• Large induced degenerate subgraphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time
• Multiplying matrices faster than coppersmith-winograd
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• New upper bounds for the problem of maximal satisfiability
• Set partitioning via inclusion-exclusion
• Some optimal inapproximability results
• The complexity of satisfiability of small depth circuits
• Which problems have strongly exponential complexity?
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(15)

• Improved exact algorithms for mildly sparse instances of MAX SAT
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• \(K_4\)-minor-free induced subgraphs of sparse connected graphs
• Exact Max 2-Sat: Easier and Faster
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• Optimal 2-constraint satisfaction via sum-product algorithms
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• A new algorithm for optimal 2-constraint satisfaction and its implications
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• A faster polynomial-space algorithm for Max 2-CSP
• Local maxima and improved exact algorithm for MAX-2-SAT

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: New exact algorithms for the 2-constraint satisfaction problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437759)