Coauthors: Dritan Nace, Oana Stan, and Renaud Sirdey

In this talk, we study the problem of partitioning networks of processes under chance constraints. This problem arises in the field of compilation for multicore processors. The theoretical equivalent for the case we consider is the Node Capacited Graph Partitioning with uncertainty affecting the weights of the vertices. For solving this problem, we propose an approximate algorithm which takes benefit of the available experimental data through a sample-based approach combined with a randomized greedy heuristic, originally developed for the deterministic version. Our computational experiments illustrate the algorithm ability to efficiently obtain robust solutions.