SPOC17 "Advances in Combinatorial Optimization"

Onglets principaux

Date: 
Vendredi, 19 octobre, 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.