Solving SAT in a distributed cloud: A portfolio approach - Ngoko, Yanik; Cérin, Christophe; Trystram, Denis (Zielona Góra: Uniwersytet Zielonogórski)
We introduce a new parallel and distributed algorithm for the solution of the satisfiability problem. It is based on an algorithm portfolio and is intended to be used for servicing requests in a distributed cloud. The core of our contribution is the modeling of the optimal resource sharing schedule in parallel executions and the proposition of heuristics for its approximation. For this purpose, we reformulate a computational problem introduced in a prior work. The main assumption is that it is possible to learn optimal resource sharing from traces collected on past executions on a representative set of instances.
Keywords: resource provisioning and scheduling; parallel distributed SAT; algorithm portfolio; maximum coverage problem