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

MaRDI QIDQ4633872zbMATH OpenFDO

Authors Serge Gaspers, Gregory B. Sorkin

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496837

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• New exact algorithms for the 2-constraint satisfaction problem
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
• A faster polynomial-space algorithm for Max 2-CSP

Cited in

(4)

• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Every 2-CSP allows nontrivial approximation
• A faster polynomial-space algorithm for Max 2-CSP
• Further Reflections on a Theory for Basic Algorithms

This page was built for publication: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between

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