Abstract: A new method for solving some hard combinatorial optimization problems is suggested, admitting a certain reformulation. Considering such a problem, several different similar problems are prepared which have the same set of solutions. They are solved on computer in parallel until one of them will be solved, and that solution is accepted. Notwithstanding the evident overhead, the whole run-time could be significantly reduced due to dispersion of velocities of combinatorial search in regarded cases. The efficiency of this approach is investigated on the concrete problem of finding short solutions of non-deterministic system of linear logical equations.

Keywords: combinatorial problems, combinatorial search, parallel computations, randomization, run-time, acceleration.

ACM Classification Keywords: G.2.1 Combinatorics – combinatorial problems, combinatorial search, G.3 Probability and Statistics – randomization, G.4 Mathematical software – efficiency, parallel and vector implementations.

Link:

RANDOMIZED PARALLELIZATION – A NEW METHOD FOR SOLVING HARD COMBINATORIAL PROBLEMS

Arkadij Zakrevskij

http://www.foibg.com/ijita/vol13/ijita13-3-p01.pdf