A Las Vegas algorithm for satisfiable SAT formulas, with an application to timetabling
Source: arxiv.org/abs/2611.18720
Many scheduling problems need many different feasible timetables, and a view of how much freedom each event has. We study a Las Vegas algorithm that samples satisfying assignments of a Boolean formula one variable at a time: it draws each value from an estimate of its conditional probability, propagates, and restarts on a contradiction. Every output is a checked solution and comes with the exact probability of producing it. We prove that a run succeeds with probability at least $2^{-K}$, where $K$ is the expected Kullback--Leibler divergence between the true and estimated conditional…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.18720
curl -X POST /api/v1/records/arxiv/2611.18720/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18720/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'