  Multicore has emerged as a typical architecture model since its advent and
stands now as a standard. The trend is to increase the number of cores and
improve the performance of the memory system. Providing an efficient multicore
implementation for a important algorithmic kernel is a genuine contribution.
From a methodology standpoint, this should be done at the level of the
underlying paradigm if any. In this paper, we study the cases of {\em dynamic
programming} and {\em greedy algorithms}, which are two major algorithmic
paradigms. We exclusively consider directives-based loop parallelization
through OpenMP and investigate necessary pre-transformations to reach a regular
parallel form. We evaluate our methodology with a selection of well-known
combinatorial optimization problems on an INTEL Broadwell processor. Key points
for scalability are discussed before and after experimental results. Our
immediate perspective is to extend our study to the manycore case, with a
special focus on NUMA configurations.
