Mardi 12 Janvier
Heure: 
12:30  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
An Exact Semidefinite Programming Approach for the MaxMean Dispersion Problem 
Description: 
Michele Garraffa This work proposes an exact algorithm for the MaxMean Dispersion Problem (MaxMean DP), an NPhard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural nonconvex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. In general, semidefinite relaxations have been successfully used to determine tight (but usually computationally expensive) lower/upper bounds for challenging NPhard problems, such as the Quadratic Assignment Problem and the Quadratic Knapsack Problem. The semidefinite relaxation for the MaxMean DP can be further tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve MaxMean DP instances to optimality. To authors' knowledge, this is the first exact algorithm that has been proposed for this problem. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up 100 elements, while standard methods for fractional combinatorial optimization manage instances whose size is less then or equal to 75. The presented approach can be generalized to other combinatorial problems with a quadratic fractional objective and linear constraints. 
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
TBC 
Description: 
Julien Courtiel 
Mercredi 13 Janvier
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
TBC [attention, c'est un mercredi] 
Description: 
Julien Courtiel 
Lundi 18 Janvier
Heure: 
14:00  15:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Deep lexical segmentation and syntactic parsing in the easyfirst dependency framework 
Description: 
Joseph Le Roux 
Jeudi 21 Janvier
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
The CRT is the scaling limit of large random dissections 
Description: 
Bénédicte Haas 
Heure: 
14:30  17:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
L'opération de flip dans les triangulations : du stockage de données à la topologie des surfaces 
Description: 
Lionel Pournin 
Jeudi 28 Janvier
Heure: 
12:15  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Non negative matrix factorization for transfer learning 
Description: 
Ievgen Redko The ability of a human being to extrapolate previously gained knowledge to other domains inspired a new family of methods in machine learning called transfer learning. Transfer learning is often based on the assumption that objects in both target and source domains share some common feature and/or data space. If this assumption is false, most of transfer learning algorithms are likely to fail. In this work, we propose to investigate the problem of transfer learning from both theoretical and applicational points of view.
First, we introduce a theoretical framework based on the HilbertSchmidt embeddings that allows us to improve the current stateoftheart theoretical results on transfer learning by introducing a natural and intuitive distance measure with strong computational guarantees for its estimation. The proposed results combine the tightness of datadependent bounds derived from Rademacher learning theory while ensuring the efficient estimation of its key factors.
We also present two different methods to solve the problem of unsupervised transfer learning based on Nonnegative matrix factorization techniques. First one represents a linear approach that aims at discovering an embedding for two tasks that decreases the distance between the corresponding probability distributions while preserving the nonnegativity property. Second one proceeds using an iterative optimization procedure that aims at aligning the kernel matrices calculated based on the data from two tasks. 
Mardi 2 Février
Heure: 
12:30  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
A Tabu Search Heuristic for a Staff Scheduling Problem 
Description: 
Stefania Pan Scheduling problems form a very large class of optimization problems en countered in several industries and organizations of widely different kinds. The particular problem that we consider is a staff scheduling problem, which con sists of assigning activities to employees by taking into account workload re quirements and different other constraints (for instance legal, economic, or ganizational and social constraints). Staff scheduling problems are NPhard, heuristics methods are often used to deal with large scale practical problems. We focus on constraints which impose minimum and maximum duration on activities. These constraints make the problem difficult to solve. We propose a Tabu Search (TS) approach to deal with the specific staff scheduling problem taking into account workload requirements and activities duration constraints. Computational results show the effectiveness of the proposed approach compar ing CPLEX solver. 
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Generating series of the trace group, and Möbius inversion 
Description: 
Anne Bouillard 
Mardi 9 Février
Heure: 
12:30  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Primal Heuristics for BranchandPrice 
Description: 
Francois Vanderbeck Math heuristics have become an essential component in mixed integer programming (MIP) solvers. Extending generic MIP heuristics, our study outlines generic procedures to build primal solutions in the context of a BranchandPrice approach and reports on their performance. Rounding the linear relaxation solution of the DantzigWolfe reformulation, which is typically tighter than that of the original compact formulation, sometimes produces better solutions than stateoftheart specialised heuristics as revealed by our numerical experiments. We focus on the socalled diving methods and their combination with diversificationintensification paradigms such as Limited Discrepancy Search, subMIPing, relaxation induced neighbourhood search, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. Our contribution lies in proposing simple strategies to get around these technical issues. Our numerical results on Generalized Assignment, Cutting Stock, and Vertex Coloring problems sets new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context. 
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
TBC 
Description: 
Nicolas Basset 
Jeudi 11 Février
Heure: 
14:00  15:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Timed Aggregate Graph : a finite graph for model checking of Time Petri Nets 
Description: 
Amal Chamakh Time Petri Nets (TPNs) are one of the most powerful formalisms for the specification and the verification of systems involving explicit timing constraints. To deal with model checking of timed systems modeled by TPNs, we propose a new finite graph, called Timed Aggregate Graph (TAG), abstracting the behavior of bounded TPNs with strong time semantics. The main feature of this abstract representation compared to existing approaches is the encoding of the time information. This is done in a pure way within each node of the TAG allowing to compute the minimum and maximum elapsed time in every path of the graph. The TAG preserves timed traces and reachable states of the corresponding TPN and allows for onthefly verification of reachability properties. We also introduce an algorithm for a modular construction of the TAG, to better confine the state explosion problem. 
Vendredi 12 Février
Heure: 
11:00  12:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Hacking Nondeterminism with Induction and Coinduction 
Description: 
Damien Pous Finite automata are used in a wide range of verification problems. We introduce "bisimulation up to congruence" as a technique for proving language equivalence of nondeterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp which, as we show, is exploiting a weaker "bisimulation up to equivalence" technique. The resulting algorithm can be exponentially faster than the recently introduced "antichain algorithms". 
Mardi 16 Février
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
TBC 
Description: 
Benjamin Hellouin 
Jeudi 18 Février
Heure: 
14:00  15:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Sampled Weighted MinHashing for LargeScale Topic Mining 
Description: 
Ivan Vladimir MEZA Sampled Weighted MinHashing (SWMH) is a randomized approach to automatically mine topics from largescale corpora. SWMH generates multiple random partitions of the corpus vocabulary based on term cooccurrence and agglomerates highly overlapping interpartition cells to produce the mined topics. While alternative approaches define a topic as a probabilistic distribution over the complete vocabulary, SWMH topics are subsets of such vocabulary. Interestingly, the topics mined by SWMH underlie themes from the corpus at different levels of granularity. We extensively evaluate the meaningfulness of the mined topics both qualitatively and quantitatively on the NIPS (1.7K documents), 20 Newsgroup (20K), Reuters (800K) and Wikipedia (4M) corpora. 
Vendredi 19 Février
Heure: 
11:00  12:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Relational typechecking of connected proofstructures 
Description: 
Luc Pellissier It is possible to define a typing system for Multiplicative Exponential Linear Logic (MELL): in such a system, typing judgments are of the form ? R : x : ?, where R is a MELL proofstructure, ? is the list of types of the conclusions of R, and x an element of the relational interpretation of ?, meaning that x is an element of the relational interpretation of R (of type ?). As relational semantics can be used to infer execution properties of the proofstructure, these judgment can be considered as forms of quantitative typing. We provide an abstract machine that decides, if R satisfies a geometric condition, whether the judgment ? R : x : ? is valid. Also, the machine halts in bilinear time in the sizes of R and x. 
Mardi 1 Mars
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Algèbre de Hopf cambrienne 
Description: 
Grégory Châtel En 1998, Loday et Ronco décrivent une algèbre de Hopf combinatoire dont la base est indicée par des arbres binaires. Cette algèbre possède de nombreux liens avec divers résultats antérieurs. Son produit est en particulier lié aux intervalles du treillis de Tamari, structure d'ordre partiel dont les éléments sont des arbres binaires. En 2006, Reading définit la notion de treillis cambrien d'un groupes de Coxeter. Le treillis Cambrien généralise l'ordre de Tamari en utilisant des structures arborescentes qui généralisent les arbres binaires : les arbres cambriens. Une question naturelle se pose alors : estil possible de généraliser l'algèbre de Hopf de LodayRonco aux arbres cambriens ? Dans cette présentation, j'expliquerai les résultats que nous avons obtenus avec Vincent Pilaud sur les arbres cambriens en type A. 

