Local maxima and improved exact algorithm for MAX-2-SAT

DOI10.4086/CJTCS.2018.002zbMATH Open1398.68493arXiv1610.07100OpenAlexW4235268052MaRDI QIDQ4578331FDOQ4578331

Authors: M. B. Hastings 

Publication date: 8 August 2018

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.07100

Recommendations

• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Exact algorithms for MAX-SAT
• New Upper Bounds for Maximum Satisfiability
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• A new upper bound for Max-2-SAT: A graph-theoretic approach

zbMATH Keywords

optimizationlocal maxima

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Cites Work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• On a lemma of Littlewood and Offord
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Two-dimensional weight-constrained codes through enumeration bounds
• New exact algorithms for the 2-constraint satisfaction problem
• Exact Max 2-Sat: Easier and Faster

Cited In (6)

• Average-case analysis for the MAX-2SAT problem
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Worst-case study of local search for MAX-\(k\)-SAT.
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem

This page was built for publication: Local maxima and improved exact algorithm for MAX-2-SAT

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