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

DOI10.4086/CJTCS.2018.002MaRDI QIDQ4578331zbMATHOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(6)

• Worst-case study of local search for MAX-\(k\)-SAT.
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Average-case analysis for the MAX-2SAT problem
• 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)