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

zbMATH Open1421.68079MaRDI QIDQ4633872FDOQ4633872

Authors: Serge Gaspers, Gregory B. Sorkin 

Publication date: 6 May 2019

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

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

Mathematics Subject Classification ID

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

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)