Geodesic
Theoretical Properties of a Neighborhood-based Approach for Widening
Serdica Journal of Computing, Tome 14 (2020) no. 3-4, pp. 65-91.

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

Most of the research in parallel data mining and machine learning algorithms is focused on improving the efficiency of existing algorithms. However, our focus is the improvement of the solution quality, or model accuracy. We are looking for "smart" strategies to invest parallel compute resources in order to achieve a better exploration of the search space by exploring several solutions in parallel, referred to as Widening. In this paper, we discuss the theoretical properties of a neighborhood-based Widening using a type of neighborhoods, optimality neighborhoods and contrast this communicationless approach to the straightforward beam-like Top-k Widening approach, which requires communication. We show a bound on the number of parallel workers needed for the communicationless approach to guarantee that it has a solution of the same quality as the Top-k approach. In addition to the theoretical comparison, we experimentally compare these two approaches in terms of running time and quality of final solution, using a widened version of the greedy algorithm for set cover problem.
Keywords: Parallel Neighborhood-Based Search, Lattice Traversal, Parallel Data Mining, Widening 
@article{SJC_2020_14_3-4_a0,
     author = {Ivanova-Rohling, Violeta},
     title = {Theoretical {Properties} of a {Neighborhood-based} {Approach} for {Widening}},
     journal = {Serdica Journal of Computing},
     pages = {65--91},
     publisher = {mathdoc},
     volume = {14},
     number = {3-4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2020_14_3-4_a0/}
}
TY  - JOUR
AU  - Ivanova-Rohling, Violeta
TI  - Theoretical Properties of a Neighborhood-based Approach for Widening
JO  - Serdica Journal of Computing
PY  - 2020
SP  - 65
EP  - 91
VL  - 14
IS  - 3-4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2020_14_3-4_a0/
LA  - en
ID  - SJC_2020_14_3-4_a0
ER  - 
%0 Journal Article
%A Ivanova-Rohling, Violeta
%T Theoretical Properties of a Neighborhood-based Approach for Widening
%J Serdica Journal of Computing
%D 2020
%P 65-91
%V 14
%N 3-4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2020_14_3-4_a0/
%G en
%F SJC_2020_14_3-4_a0
Ivanova-Rohling, Violeta. Theoretical Properties of a Neighborhood-based Approach for Widening. Serdica Journal of Computing, Tome 14 (2020) no. 3-4, pp. 65-91. http://geodesic.mathdoc.fr/item/SJC_2020_14_3-4_a0/