SPOC17 "Advances in Combinatorial Optimization"
Primary tabs
Date:
Friday, 19 October, 2018
17ème séminaire du groupe POC
Le VENDREDI 19 OCTOBRE 2018
Au laboratoire LIP6 de Sorbonne Université (ex-UPMC-Paris VI)
Campus Pierre et Marie Curie (Jussieu)
4 place Jussieu (métro Jussieu)
Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105
Sur le thème
"Advances in Combinatorial Optimization"
Ce séminaire est libre d'accès mais merci de vous inscrire en utilisant l'onglet situé en-haut de page pour faciliter l'organisation.
Cliquer ici pour voir la liste des inscrits
Programme de la journée:
9h30-10h00 Accueil "café-croissants"
10h00-11h00
Jon LEE, University of Michigan, USA
On sparse generalized inverses by LP, SDP and local search
The Moore-Penrose Pseudoinverse (MPP) is a key tool in data analysis.
Eg., it can be used to solve least-squares problems. But the MPP is typically dense,
and with very large data sets, we may be content with an approximation of MPP
that is much sparser. When we have a use case where we need to multiply many
vectors by the MPP, we may be willing to put in substantial effort to get a sparse
approximation. We use linear programming and semidefinite programming to
define and calculate various sparse generalized inverses, and we use a local-search
scheme to derive a relevant polynomial-time approximation algorithm.
This is joint work with Marcia Fampa (UFRJ) and Victor Fuentes (UM).
11h00 - 11h15 Pause
11h15 - 12h15
Giovanni RINALDI, IASI-CNR, Roma, Italy
The Max-Cut problem: challenges from quantum computing
The Max-Cut problem is the one of finding a maximum weight cut in a
weighted graph. Because of its great interest among the optimizers,
several approaches, also of a quite diverse nature, have been proposed
to find good or provably good solutions, which makes it also very
interesting as a benchmark problem for new algorithmic ideas. Very
recently the problem has received a lot of attention since a dedicated
hardware, based on quantum annealing, has been realized that yields good
solutions in amazingly short times for some particular instances (the
Chimera graphs). We review some of the exact optimization algorithms
today available and some challenging instances originated by the quantum
approach.
12h15-14h00 Repas
A partir de 14h00 dans la même salle
Soutenance de l'HDR de Pierre FOUILHOUX, Sorbonne Université, Paris
"Linear Formulations and exact algorithms for Combinatorial Optimization"
Pour plus de renseignements, cliquez-ici.