Nos tutelles

CNRS

Nos partenaires


Accueil > Actualités > Séminaires > Archives Séminaires

Séminaires passés 2016-2017


- Anan Phonphoem - KU, Thaïlande - Wireless Network Application for Wildlife Conservation and Disaster Monitoring
Public : grand public

Jeudi 6 juillet 2017 - 13 h 00 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence

This talk will provide the examples of wireless application in the
Wildlife Conservation and Disaster Monitoring. For Wildlife
Conservation, the camera trap with wireless trigger capability and
smart patrol system will be presented. The landslides
monitoring/alarming system deployed in Krabi province, Thailand, will
be explained as the example of wireless sensor network deployment in
Disaster area.
Site :https://www.cpe.ku.ac.th/~anan/myhomepage/?page_id=71


- Oscar Salviano Silva Filho - PUC, Brésil - On an Optimal Production-Inventory Plan for a Closed Loop Supply Chain
Public : grand public

Jeudi 6 juillet 2017 - 14 h 00 - 14 h 30 - Salle du Conseil - Bâtiment ISIMA

In order to provide middle and long-term inventory-production plans, a chance constraint, stochastic quadratic problem subject to linear discrete-time inventory-production systems is formulated. The idea is to meet the demand for a single product, which can be manufactured from a forward channel and refurbished from a backward channel. The random nature of demand fluctuation affects the variability of serviceable inventory variable in the sense of its variance increases over periods of planning horizon. In order to mitigate such variability, a feedback gain that relates refurbished rate to serviceable inventory level is provided from a minimum variance problem. As a result, an optimal production plan is developed from an equivalent constrained Mean Value problem regulated by this gain. A simple example illustrates mains results.

Site : https://www.researchgate.net/profile/Oscar_Salviano
Biography
Oscar Salviano Silva Filho is with Pontific Catholic University of Campinas ((PUCCAMP), where give lectures and advice student on
business logistics and operations research issues. He received his M.Sc and PhD titles in Automation System from State University of
Campinas (UNICAMP) in 1982 and 1989, respectively. Currently, his research interests topics includes logistics, supply chain, operations
research, collective inteligence and actives learning education.


- Frédéric Andres - NII, Japon
Public : grand public

Jeudi 6 juillet 2017 - 14 h 30 - 15 h 00 - Salle du Conseil - Bâtiment ISIMA

Site : http://www.nii.ac.jp/en/faculty/digital_content/andres_frederic/


- Daniel GONCALVES - LIRMM à Montpellier - Every 3-colorable planar graphs is the intersection graph of some segments having slope in (0 , pi/3 , 2 pi/3)

Jeudi 29 juin 2017 - 13 h 00 - Salle du Conseil - Bâtiment ISIMA

We will present the proof of the above theorem, which partially answers a question raised by De Fraysseix and Ossona de Mendez. Their open problem is, "Is every $k$-colorable planar graph the intersection graph of segments using $k$ slopes ?". It was known to hold for $k=2$. Here we prove the case $k=3$. The case $k=4$ is open and is also known as West’s conjecture. As in these intersection models, parallel segments are expected to be pairwise disjoint, this conjecture generalizes both the 4-color theorem and the fact that every planar graph is an intersection graph of segments.

A crucial point in our proof is the use of a system of linear equations, which provides a scheme of the solution. It is shown that this system always has a (unique) solution by studying the perfect matchings of some related planar graph.

At the end of the talk we will briefly discuss how West’s conjecture could be tackled using a similar approach.


-  Emmanuel Coquery (Université Lyon 1, LIRIS) - Réécriture de requêtes pour le contrôle d’accès.

Jeudi 8 juin 2017 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

L’utilisation de vues est un moyen classique de contrôler de manière fine l’accès à des données relationnelles.
Par ailleurs, il peut être intéressant de précalculer le résultat de certaines requêtes sous forme de vues matérialisées, soit à des fins d’optimisation, soit pour exporter une partie des données sur un autre serveur.
Il devient alors compliqué de mettre au point des vues pour contrôler l’accès à ces vues matérialisées.
Après avoir introduit les algorithmes classiques d’intégration de données, en particulier Minicon, nous montrerons ici comment ils peuvent être utilisés afin de construire des vues de contrôle d’accès sur ces vues matérialisées.


- Manik Lal Das (DA-IICT) - Ganghinagar, India, Key Escrow free Identity-based Cryptosystem

Jeudi 1er juin 2017 - 14 h 00 - Amphi B - IUT - Séminaire confiance numérique

Over the years, several identity-based cryptosystems using bilinear pairings have been proposed. Many schemes, based on bilinear pairings, suffer from key escrow problems and require a secure channel for private key issuance. In this talk, we will discuss on a binding-blinding technique, which can be used for solving the problem of key escrow in identity-based cryptosystem and can help in eliminating the requirement of secure channel for the private key issuance.


- Pierre BERNHARD (Directeur de recherches émérite - l’INRIA Sophia-Antipolis) - "Sélection sexuelle : le principe du handicap et la dynamique adaptative."

Jeudi 18 mai 2017 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Le "paradoxe du handicap" a été remarqué par Charles Darwin lui-même : il consiste en ce que des caractères sexuels secondaires, généralement chez les mâles, qui semblent attirer les individus du sexe opposé, généralement les femelles donc, constituent, dans leur développement apparemment excessif, un handicap de viabilité pour les individus qui les portent. Darwin en a déduit l’existence d’un phénomène de "sélection sexuelle" à côté de la "sélection naturelle", la réussite d’une lignée évolutive dépendant non seulement de la viabilité des individus, mais aussi de l’efficacité de son système d’appariement sexuel.

Nous examinerons l’explication la plus communément admise, en termes de jeux de signaux, et proposerons un modèle mathématique dont nous pouvons, d’une part déterminer l’équilibre complet, et d’autre part montrer comment ce équilibre peut être atteint par la dynamique de l’évolution.


- Florian RICHOUX (MCF au Laboratoire des Sciences du Numérique de Nantes) - Game AI et problèmes d’optimisation

Jeudi 13 Avril 2017 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Les jeux s’avèrent être des terrains pratiques pour tester des méthodes d’intelligence artificielle, que ce soit en apprentissage automatique, en représentation des connaissances et raisonnement ou encore en résolution de problèmes, notamment d’optimisation. Il s’agit aussi d’un domaine où une solide industrie est en place, avec ses attentes et ces besoins en matière de résolution de problèmes. Après avoir donné un rapide tour d’horizon de la recherche en Game AI, je présenterai le framework GHOST conçu pour que des développeurs puissent facilement modéliser leur problèmes d’optimisation sous la forme de problèmes de contraintes. GHOST inclut un solveur de problèmes de contraintes visant des temps agressifs d’exécution (de l’ordre de 10ms) afin d’être exploitable dans des environnements nécessitants de temps très courts de prise de décision, comme les jeux vidéo par exemple.

Séminaire Florian RICHOUX

Monitoring


- Thomas BELITTO ( (Université Bordeaux 1, LABRI) - Autour du problème de Traffic Monitoring

Jeudi 30 mars 2017 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Dans le cadre du problème du Traffic Monitoring, on modélise un réseau par un graphe orienté et on a la possibilité de munir de capteurs les arcs de ce graphe. Lorsqu’un objet circule dans le réseau, il active un capteur à chaque fois qu’il passe par un arc équipé et la séquence ordonnée des capteurs qu’il a activés constitue ce que l’on appelle la signature de la marche de l’objet. Les données du problème sont un graphe orienté (éventuellement pondéré) et un ensemble de marches sur le graphe que l’objet peut prendre. L’objectif est de chercher le plus petit ensemble d’arcs (ou le moins coûteux) à munir de capteurs tel que toutes les marches possibles aient des signatures différentes et qu’on soit ainsi capable de reconstituer exactement la trajectoire de l’objet à partir des informations envoyées par les capteurs. L’étude de ce problème nous amènera à étudier dans un premier temps la notion proche de code séparateur et à développer des modèles plus puissants. Le problème de Traffic Monitoring étant NP-complet en la taille de l’ensemble des marches à distinguer (qui peut être infini), il est exclu de le résoudre dans le cas général mais nous nous demanderons quels ensembles de marches peuvent avoir un intérêt pratique et chercherons des propriétés de ces ensembles qui nous permettront de mettre au point des algorithmes plus efficaces. Ces considérations nous conduiront notamment à étudier les graphes à transitions interdites qui sont particulièrement pratiques pour modéliser les réseaux routiers.


- Prof. Dario Landa Silva (Université de Nottingham) - Optimisation Techniques for Workforce Scheduling and Routing Problems

Jeudi 30 mars 2017 - 11 h 00 - Salle du conseil - Bâtiment ISIMA

SEMINAIRE ANNULE

In the context of workforce scheduling, there are many scenarios in which personnel must carry out tasks at different locations hence requiring some form of transportation. Examples of this type of scenarios include nurses visiting patients at home, technicians carrying out repairs at customers’ locations, security guards performing rounds at different premises, etc. These mobile workforce scheduling scenarios involve the scheduling of personnel combined with some form of routing. First, this talk presents a survey of this type of problems and solution methods. We identify the key features of these problems and the range of solution techniques that have been applied to tackle them. Next, the talk describes a study on the computational difficulty of solving this type of problems. This study aims to understand the challenges that these problems present to optimization techniques. Finally, the talk presents some ongoing work on the development of practical solutions methods to tackle these large and difficult problems in a variety of real-world scenarios faced by our industrial partner, a provider of mobile workforce scheduling and management software.


- Nicolas JOZEFOWIEZ (Université de Toulouse, INSA et LAAS-CNRS) - Avancées en programmation linéaire en nombres entiers bi-objectif : calcul de bornes inférieures par génération de colonnes

Jeudi 23 mars 2017 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Depuis une dizaine d’années, les travaux sur la programmation linéaire en nombres entiers bi-objectif prennent de plus en plus d’importance notamment sur les méthodes de recherche arborescente et sur le calcul de bornes inférieures. Dans ce séminaire, après une introduction à l’optimisation multi-objectif, certaines des questions qui se posent actuellement seront présentées. Puis, un focus sera fait sur le calcul de bornes inférieures par algorithme de génération de colonnes. Cette méthode a connu un développement important en optimisation combinatoire notamment pour les problèmes de tournées de véhicules. Toutefois, il existe peu d’études sur son utilisation en optimisation combinatoire multi-objectif. Finalement, un exemple sera fait sur des problèmes de tournées avec couverture. Ces problèmes, qui ont une application en logistique humanitaire, offrent un parfait exemple de problèmes naturellement bi-objectif.


- Guillaume TOUYA (IGN) - Panorama des recherches en géovisualisation à l’IGN et interfaces avec la recherche en informatique

Jeudi 16 mars 2017 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

La géomatique est une discipline à l’interface entre l’informatique et la géographie et regroupe toutes les disciplines traitant de la saisie, de la modélisation et de l’utilisation des données ayant une composante spatiale. Parmi ces disciplines, la géovisualisation traite de la visualisation des données spatialisées et des interactions avec ces visualisations. Les travaux en géovisualisation à l’IGN cherchent par exemple à automatiser le changement d’échelle d’une carte, qu’elle soit visualisée sur écran ou imprimée sur papier, à reproduire le style d’un artiste ou de cartes anciennes avec des données actuelles, ou à plaquer des images prises depuis une voiture sur un vrai modèle de bâtiments en 3D. Ces recherches empruntent des techniques, et même parfois contribuent à différents domaines de l’informatique : visualisation d’information, recherche opérationnelle, systèmes multi-agents, interactions homme machine ou algorithmie géométrique.


- Jean-Philippe GAYON, Laboratoire G-SCOP Grenoble) - Gestion des avions dans un aéroport : ordonnancement à la piste, routage et affectation aux points de stationnement

Jeudi 9 mars 2017 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Nous nous intéressons à la gestion des opérations au sol des avions. Ce projet est conduit en partenariat avec la société Amadeus et deux aéroports européens. L’objectif est de mieux coordonner les opérations au sol, afin de réduire la congestion et ainsi augmenter la capacité des aéroports. Nous considérons en particulier trois problèmes : l’ordonnancement des décollages et atterrissages, le routage des avions entre les pistes et les points de stationnement et enfin l’affectation des avions aux portes. Nous montrons comment modéliser et résoudre ces problèmes indépendamment. Ces trois problèmes, pris séparément, donnent des solutions peu satisfaisantes en pratique. Nous proposons des pistes afin d’intégrer ces trois problèmes et ainsi mieux coordonner les différentes opérations au sol. Les outils de modélisation mis en oeuvre sont la programmation linéaire en nombres entiers et la théorie des files d’attente.


- Quentin BRAMAS (ATER au LIP6) - L’agrégation de données dans les graphes dynamiques.

Jeudi 16 Février 2017 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Les graphes dynamiques, aussi appelés graphes évolutifs, graphes temporels ou graphes variant dans le temps, ont gagné en popularité car il permettent de modéliser un grand nombre de phénomènes, et plus particulièrement les interactions dans les réseaux dont la topologie évolue rapidement, comme les réseaux de capteurs sans fil, les protocoles de population, ou bien les réseaux sociaux.
Dans un graphe dynamique, les noeuds et les arrêtes apparaissent et disparaissent au fil du temps, et ces changements ne sont pas vus comme des fautes mais bien comme une caractéristique à part entière du graphe.
Dans cette présentation, je vais montrer plusieurs manières de définir les graphes dynamiques et quelles sont leurs propriétés. Enfin, je présenterai à titre d’exemple mes contributions sur le problème de l’agrégation de données dans les graphes dynamiques, d’un point de vue centralisé ou distribué, avec connaissance du futur ou non.


- M. Viet Hung Nguyen (LIP6) - Reduced-size formulations for metric and cut polyhedra in sparse graphs

Jeudi 26 Janvier 2017 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Given a graph G=(V,E) of n vertices and m edges, we consider the metric cone MET(G) and the metric polytope METP(G) defined on the real space indexed by E.
These polyhedra are relaxations of several important problems in combinatorial optimization such as the max-cut problem and the multicommodity flow problem.
They are known to have non-compact formulations via the cycle inequalities in the original space inline image and compact (i.e., polynomial size) extended formulations
via the triangle inequalities defined on the complete graph of n vertices. In this talk, we show that one can reduce the number of triangle inequalities to O(nm) and
still have extended formulations for MET(G) and METP(G). We also present several extensions of the result for special graphs and for graph partitioning problem.


- Guilherme Da Fonseca (LIMOS) - Optimal Approximate Polytope Membership

Jeudi 8 décembre 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Joint work with Sunil Arya and David M. Mount to appear in SODA 2017.
In the polytope membership problem, a convex polytope K in d-dimensional space is given, and the objective is to preprocess K into a data structure so that, given a query point q, it is possible to determine efficiently whether q is inside K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter eps > 0, the query can be answered either way if the distance from q to K’s boundary is at most eps times K’s diameter. Previous solutions to the problem were on the form of a space-time trade-off. In this paper, we present a data structure that simultaneously achieves logarithmic query time and minimum storage of O(1/eps^(d-1)/2). Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer eps-approximate nearest neighbor queries for a set of n points in logarithmic time is reduced to O(n/eps^d/2). This halves the exponent in the eps-dependency of the existing space bound of roughly O(n/eps^d), which has stood for 15 years (Har-Peled, 2001).


- Aurélie Lagoutte (G-SCOP Grenoble) - Coloring perfect graphs with bounded clique number.

Jeudi 24 novembre 2016 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Perfect graphs are graphs for which the chromatic number matches the trivial lower bound consisting in the clique number (and the same holds for every induced subgraph). After the long study that led to the Strong Perfect Graph Theorem, the main open question concerning them is about finding an optimal coloring with a combinatorial algorithm.
Indeed, deciding if the chromatic number of a graph is at most k is NP-complete in general, and even if k=3. A famous result of Lovasz, Grötchel and Schrijver provides a polynomial-time algorithm that optimally colors any perfect graph, however this algorithm uses the ellipsoid method which makes it unpractical and not combinatorial.
We design a purely combinatorial algorithm that, given in input a perfect graph, outputs an optimal coloring in time O(n^f) where f is quadratic in the clique number omega(G).

This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.


- Michel BALINSKI (Ancien membre Laboratoire d’Econométrie - Ecole Polytechnique) - Le jugement majoritaire : Un nouveau mode de scrutin

Jeudi 10 novembre 2016 - 14 h 00 - Amphi 3 du pôle commun

Tous les modes de scrutin traditionnel y compris le scrutin majoritaire à un ou à deux tours échouent en pratique : souvent sont élus des candidats autres que celui réellement voulu par l’électorat (parmi les multiples exemples : Bill Clinton en 1992, George W. Bush en 2000, Jacques Chirac en 2002, Nicolas Sarkozy en 2007).

Le scrutin majoritaire peut se tromper même dans un face-à-face entre deux candidats. Le modèle traditionnel de la théorie du vote – ou de la théorie du choix sociale – échoue aussi et pour la même raison : le choix d’expression d’opinion offert à l’électeur est inadéquate.

Le jugement majoritaire donne aux électeurs la possibilité de s’exprimer pleinement et répond le mieux aux critères traditionnels et de bon sens de ce qui constitue une bonne méthode de vote.

Ces propos seront argumentés, exemples réels et théorèmes à l’appui.

Références :

Michel Balinski et Rida Laraki. 2007. « A theory of measuring, electing, and ranking ». Proceedings of the National Academy of Sciences, USA 104 8720-8725.

— et —. 2010. Majority Judgment : Measuring, Ranking, and Electing. MIT Press.

— et —. 2013. « Jugement majoritaire versus vote majoritaire (via les présidentielles 2011-2012) ». Revue Française d’Economie XXVII 11-44.

— et —. 2014. « Judge : Don’t vote ! » Operations Research 62 483-511.

— et —. 2016. « Pour éviter un nouveau 21 avril, instaurons le jugement majoritaire ». TheConversation, 21 avril. https://theconversation.com/pour-eviter-un-nouveau-21-avril-instaurons-le-jugement-majoritaire-58178

— et —. 2016. « Trump and Clinton victorious : proof that US voting system doesn’t work ». TheConversation, 9 mai. https://theconversation.com/trump-and-clinton-victorious-proof-that-us-voting-system-doesnt-work-58752

— et —. 2016. « Majority judgment vs. Majority rule ». Working paper.

- Dr. Warith Eddine JEDDY (INSAT Kasserine, Tunisie) - Approche globale d’alignement pour les réseaux d’interaction protéine-protéine

Jeudi 13 octobre 2016 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

Pas de visio-conférence

Les protéines et leurs interactions sont au cœur de presque tous les processus biologiques dans une cellule vivante. Les interactions protéine-protéine (PPI) peuvent être représentées sous la forme d’un graphe dont les nœuds sont des protéines et les arêtes représentent les interactions physiques qui les relient. Les PPI jouent un rôle fondamental dans les voies de signalisation qui régulent de nombreuses fonctions cellulaires. Leur étude est donc cruciale pour la compréhension des réseaux d’interaction protéiques, but majeur dans l’étude des systèmes biologiques. L’alignement multiple de réseaux PPI a pour objectif d’extraire des informations fonctionnelles des interactions entre protéines. Dans cette présentation, nous proposons une formalisation de notre algorithme pour l’alignement multiple de plusieurs réseaux PPI. Notre approche d’alignement de réseaux peut être locale ou globale, et peut s’appliquer à plus de deux réseaux simultanément afin de trouver des structures communes (i.e. chemins, zones denses,...) apparaissant dans chacun des deux réseaux.

- Lucas Pastor (G-SCOP , Grenoble) - Disproving the normal graph conjecture

Mercredi 12 octobre 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence

A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a stable set, and every clique of C intersects every stable set of S. De Simone and Körner conjectured in 1999 that a graph G is normal if G does not contain C_5, C_7 and the complement of C_7 as an induced subgraph. By using probabilistic methods we disprove this conjecture.

This is joint-work with Ararat Harutyunyan (University of Toulouse III) and Stéphan Thomassé (ENS Lyon).


- Reza NASERASR (LRI - Univ. Paris XI) - Bounding K_4 minor free graphs in homomorphism order

Jeudi 29 septembre 2016 - 14 h 00 - Amphi Bruno Garcia - Bâtiment ISIMA

Pas de visio-conférence

We give an algorithm which decides if a given graph B of odd-girth 2k+1 admits a homomorphism from each K_4-minor free graph of odd-girth 2k+1. The runing time is O(|V(B)|^3). Moreover the algorithm is theoretically used to find families of bounds. As an application of one such family of bounds we show that fractional chromatic number of any $K_4$-minor free graph of odd-girth 2k+1 is 2+1/k.

This is a joint work with Laurent Beadou and Florent Foucaud.


- Marta SOARE (Univ. of Aalto, Finlande) - Sequential Decision Making in Linear Bandit Setting

Jeudi 29 septembre 2016 - 15 h 30 - Amphi Bruno Garcia - Bâtiment ISIMA

Pas de visio-conférence

When making a decision in an unknown environment, a learning agent decides at every step whether to gather more information on the environment (explore), or to choose what seems to be the best action given the current information (exploit). The multi-armed bandit setting is a simple framework that captures this exploration-exploitation trade-off and offers efficient solutions for sequential decision making. In this talk, I will review a particular multi-armed bandit setting, where there is a global linear structure in the environment. I will then show how this structure can be exploited for finding the best action using a minimal number of steps and for deciding when to transfer samples to improve the performance in other similar environments.