Geodesic
Incomplete algorithms in the large-block parallelism of combinatorial problems
Numerical methods and programming, Tome 9 (2008) no. 1, pp. 108-118

Voir la notice de l'article provenant de la source Math-Net.Ru

A technique for solving some types of NP-hard combinatorial problems by incomplete algorithms (i.e., the algorithms that are not generally guaranteed to be finite) is studied. The case in point is “programming in constraints” that uses the idea of updating the base of constraints along with the rejection of irrelevant constraints. Two approaches to some combinatorial problems solved by the incomplete algorithms are compared. The first approach is based on the large-block parallelization of the original problem with the subsequent solving of the resulting problems by an incomplete algorithm on a cluster. In the second approach, the original problem is solved on a single processor of the cluster (actually on a PC computer) by the same algorithm. It is shown that in some cases the speedup factor reached in the first approach can substantially exceed the number of processors in the cluster. The work was supported by the Russian Foundation for Basic Research (project N 07-01-00400a). The paper was prepared on the basis of the authors' report at the International Conference on Parallel Computing Technologies (PaVT-2008; http://agora.guru.ru/pavt).
Keywords: base of constraints, incompleteness, large-block parallelism, constraint programming, parallel programs.
Mots-clés : decomposition 
@article{VMP_2008_9_1_a14,
     author = {A. A. Semenov and O. S. Zaikin},
     title = {Incomplete algorithms in the large-block parallelism of combinatorial problems},
     journal = {Numerical methods and programming},
     pages = {108--118},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2008_9_1_a14/}
}
TY  - JOUR
AU  - A. A. Semenov
AU  - O. S. Zaikin
TI  - Incomplete algorithms in the large-block parallelism of combinatorial problems
JO  - Numerical methods and programming
PY  - 2008
SP  - 108
EP  - 118
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2008_9_1_a14/
LA  - ru
ID  - VMP_2008_9_1_a14
ER  - 
%0 Journal Article
%A A. A. Semenov
%A O. S. Zaikin
%T Incomplete algorithms in the large-block parallelism of combinatorial problems
%J Numerical methods and programming
%D 2008
%P 108-118
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2008_9_1_a14/
%G ru
%F VMP_2008_9_1_a14
A. A. Semenov; O. S. Zaikin. Incomplete algorithms in the large-block parallelism of combinatorial problems. Numerical methods and programming, Tome 9 (2008) no. 1, pp. 108-118. http://geodesic.mathdoc.fr/item/VMP_2008_9_1_a14/