Beating the random assignment on constraint satisfaction problems of bounded degree

DOI10.4230/LIPICS.APPROX-RANDOM.2015.110MaRDI QIDQ5351893zbMATH OpenFDO

Authors

Publication date 31 August 2017

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

zbMATH Keywords

advantage over randombounded degreeconstraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• A better algorithm for random \(k\)-SAT
• A Better Algorithm for Random k-SAT
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited in

(4)

• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Computing the partition function of a polynomial on the Boolean cube
• A practitioner’s guide to quantum algorithms for optimisation problems
• Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs

This page was built for publication: Beating the random assignment on constraint satisfaction problems of bounded degree

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