Mars 2014


Retour à la vue des calendrier
Mardi 4 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Problème de placement orthogonal
Description: Petru Valicov Etant donné un conteneur rectangulaire C, on s'intéresse à
décider si un ensemble d'items rectangulaires peut être placé sans
chevauchement et sans dépassement des bords de C. Une contrainte
supplémentaire est prise en compte -- l'interdiction de rotation des
items. Ce problème est NP-complet et est un sous-problème du problème de
sac-à-dos orthogonal où à chaque item on associe un profit et on cherche
le sous-ensemble d'items réalisable de profit total maximum. Fekete et
Schepers ont introduit une caractérisation élégante des solutions du
problème de placement en utilisant les graphes d'intervalles. Nous
présentons une nouvelle caractérisation en utilisant des MPQ-arbres --
des structures de données qui encodent efficacement les graphes
d'intervalles. Un des principaux avantages de cette caractérisation est
un nombre plus restreint des solutions symétriques traitées lors de
l'exécution de l'algorithme. Nous finiront par présenter une comparaison
des résultats avec ceux de la littérature sur les jeux de données
connus. Travail effectué en collaboration avec C. Joncour et A. Pêcher.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Rationality of growth in the Heisenberg groups
Description: Moon Duchin I'll discuss the history of work on the question of how andwhether rationality of growth depends on generators. That is, for afinitely generated group, one can study the growth function (the number ofwords spellable in up to n letters) and its growth series, the associatedgenerating function. This growth series is itself a rational function whenthere is a recursive relationship among the values of the growth function. It is known that all virtually abelian groups and all hyperbolic groupshave rational growth in any generators, by work of Benson and Cannonrespectively. Work of Shapiro and of Stoll sheds some light on thesituation in nilpotent groups, but shows it to be more complicated-- evenfor the second Heisenberg group H_5, some generators give rational growthbut others do not. I'll describe work in progress with Shapiro givinggeometric arguments to establish rationality in all generators for theclassical Heisenberg group H_3.
Vendredi 7 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lambda-calculus and the Invariance Thesis
Description: Beniamino Accattoli








reasonable λλλλsize
explosion problemλλimpasse usefulβi.e.
Mardi 11 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Convolution de Dirichlet et énumération de pyramides et espaliers
Description: Matthieu Deneufchâtel Nous étudions l'énumération de deux familles de polycubes, lespyramides et les espaliers, en lien avec une version multi-indexée de laconvolution de Dirichlet.
Vendredi 14 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: On type isomorphisms in simultaneous presence of sums and functions
Description: Danko Ilik We consider the problem of characterizing isomorphisms of types, or, equivalently, constructive cardinality of sets, in the simultaneous presence of disjoint unions, Cartesian products, and exponentials. Mostly relying on results about polynomials with exponentiation that have not been used in our context, we derive: that the usual finite axiomatization known as High-School Identities (HSI) is complete for a significant subclass of types; that it is decidable for that subclass when two types are isomorphic; that, for the whole of the set of types, a recursive extension of the axioms of HSI exists that is complete; and that, for the whole of the set of types, the question as to whether two types are isomorphic is decidable when base types are to be interpreted as finite sets. We also point out certain related open problems.
Mardi 18 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques projets autour de méthodes de génération de colonnes et d'algorithmes mémétiques
Description: Daniel Porumbel Après une introduction générale, la première partie de cette communication présentera en lignes générales quelques travaux sur deux axes de recherche. 1.Bornes duales à base de méthodes de génération de colonnes Deux projets sont évoqués:  1.A. Génération de Colonnes à Base d'un (Sous-)Problème d'Intersection    De point de vue dual, la génération de colonnes fonctionne comme une méthode à     base de plans sécants (e.g., "Kelley's cutting plane") dans le polytope dual P.     Pour ajouter itérativement des contraintes duales (colonnes), la génération de    colonnes fait appel à un sous-problème de séparation sur P. On propose une     méthode qui permet d'optimiser P en faisant appel à un sous-problème d'inter-    section au lieu du sous-problème de séparation.  Ce sous-problème d'intersection    demande d'avancer sur la direction 0->r d'un "rayon" r jusqu'au moment où on     intersecte une facette de P. On génère une séquence de rayons r1, r2, ... qui    convergent vers 0->OPT(P) où P est la solution dual optimale. Des résultats seront    présentés pour quelques versions de Cutting-Stock et sur Arc-Routing 1.B. Méthodes d'agrégation duale    Pour réduire la taille du polytope dual P, nous avons groupé et agrégé les variables    duales en k groups. Cela permet d'obtenir un polytope agrégé Pk complètement     inclus dans P. On augment k itérativement, et ainsi, OPT(Pk) converge vers OPT(P).2. Bornes primales à l'aide d'algorithmes "Spacing Memetic"    Dans ce travail, nous proposons une méthode à base de distances entre solutions    candidates pour contrôler la diversité de la population d'un algorithme mémétique.    L'approche possède des similarités avec "MA|PM" (Memetic Algorithms with Population Management).      La deuxième partie présente plus en détail le projet 1.A. ci-dessus, suivi de différentesperspectives.
Vendredi 21 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Can Dialectica break bricks?
Description: Pierre-Marie Pédrot
The Dialectica translation is a logical transformation described by
Gödel in 1958, but designed in the 30's. At the end of the 80's, it was
given a categorical counterpart, which happened to be compatible with
the usual decomposition of intuitionistic logic into linear logic.
Still, it was lacking a true Curry-Howard interpretation.
We will fill this hole by presenting the computational content of
Dialectica by means of an untyped lambda-calculus translation. We will
show that this translation has a really simple explanation as soon as we
put our source term in the Krivine abstract machine, except for a
disturbing detail, seemingly deeply rooted in linear logic. We will also
show how our presentation can be naturally applied to a
dependently-typed system almost without adaptation, thus giving a
hindsight on how linear dependent types may be built (or not).
Mardi 25 Mars
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The robust vehicle routing problem with time windows and travel time uncertainty
Description: Rosa Figueiredo This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem
that arises in maritime transportation where delays are frequent and
should be taken into account. Our model only allows routes that are
feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different decomposition approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. The formulation is solved by a row-and-column generation algorithm. The second formulation generalizes a path inequalities formulation to the
uncertain context and is solved through a row generation algorithm. In
particular, we discuss efficient separation procedures. We compare the two formulations on maritime transportation instances.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Autour des automates cellulaires probabilistes
Description: Irène Marcovici Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage.Je présenterai les résultats obtenus au cours de ma thèse sur deux "problèmes inverses" : le premier consiste à étudier les ACP ayant des mesures invariantes de forme produit de Bernoulli ; le second est le problème de la classification de la densité, qui consiste à trouver un AC(P) dont l'évolution permette de distinguer une configuration initiale sur l'alphabet binaire tirée selon une mesure de Bernoulli de paramètre inférieur ou supérieur à 1/2, et que nous avons résolu sur les grillesde dimension supérieure ou égale à 2 et sur les arbres.
Vendredi 28 Mars
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Interaction Graphs and Complexity
Description: Thomas Seiller We obtained, with C. Aubert, new characterizations of complexity classes
coNL and L using methods inspired from Girard's hyperfinite Geometry of
Interaction (GoI). These characterizations had some drawbacks, among which:
- it used complicated tools from operator theory;
- it was not related to the interpretation of logic in the Geometry of
Interaction construction;

This work revisits these previous results by using Interaction Graphs, a
combinatorial GoI construction developed during my thesis that
simplifies, unifies and generalizes Girard's GoI constructions. This
change of perspective allows for a number of improvements, namely:
- the obtention of simplified characterizations of the classes coNL and L;
- the obtention of new characterizations, e.g. Regular languages, NL;
- it relates the method to the reconstruction of logic in Interaction
Graphs (hence in GoI);
- it offers new ways to obtain characterizations of other classe.