2014


Retour à la vue des calendrier
Mardi 7 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Pavages auto-assemblants avec et sans coopération
Description: Pierre-Étienne Meunier Les pavages auto-assemblants sont un modèle de formation de structures moléculaires, dans lequel on peutsimuler des machines de Turing. Il s'agit essentiellement d'une modification des tuiles de Wang, où l'on rajoute un mécanisme de formation des pavages.Je présenterai dans cet exposé deux résultats de séparation entre deux variantes de ce modèle : le modèle coopératif, où certaines tuiles ne peuvent s'assembler avec le reste du pavage que si plusieurs de leurs côtés correspondent, et le modèle non-coopératif, où toutes les tuiles peuvent s'assembler si au moins un de leurs côtés correspond.
Mardi 14 Janvier
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An Exact Placement Approach for Optimizing Cost and Recovery Time under Faulty Multi-Cloud Environments
Description: Felipe Di­az Sanchez Currently, Cloud brokers bring interoperability and portability of
applications across multiple Clouds. In the future, Cloud brokers will
offer services based on their knowledge of Cloud providers
infrastructure to automatically and cost-effectively overcome
performance degradation. In this paper, we present a Mixed-Integer
Linear Program (MILP) that provides a cost-effective placement across
multiple Clouds. Our MILP formulation considers parameters of Cloud
providers such as price, configuration of VMs, network latency, and
provisioning time. We evaluate the cost-effectiveness of deploying a
Cloud infrastructure into a single or across multiple Cloud providers
by using real prices and VM configurations. The results show that in
some cases may be cost-effective to distribute the infrastructure
across multiple Cloud providers. We also propose three placement
policies for faulty multi-Cloud scenarios. The best of these policies
minimizes the cost of the Cloud infrastructure under fixed
provisioning time values.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Convolution de Dirichlet et énumération de pyramides
Description: Olivier Mallet Dans cet exposé, on introduit deux familles de polycubes : lespyramides et les espaliers. On calcule les séries génératricesordinaire et de Dirichlet de ces objets à l'aide d'une versionmulti-indexée de la convolution de Dirichlet. On s'intéresse ensuite àune généralisation des pyramides et des espaliers en dimension dquelconque et on montre que le nombre de pyramides de volume fixé endimension d+1 est un polynôme en d. On explique enfin commentappliquer les techniques mises en œuvre ici à d'autres familles depolycubes.
Jeudi 16 Janvier
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Réseaux sociaux et "big data" : des sources historiques aux plateformes web
Description: Christophe Prieur S'il est désormais notoire que la profusion de données concernant lesindividus et leurs activités constitue la matière première d'un contrôlesans précédent, la recherche en sciences sociales se doit de s'en saisirà son tour pour mettre au point des outils d'analyse à la mesure deschangements considérables qu'elle observe. La recherche en informatiqueet en mathématiques, quant à elle, peut difficilement se soustraire à laresponsabilité qui lui incombe de donner à ses résultats un tour un tantsoit peu critique, en s'alliant avec les sciences sociales au moinsautant qu'avec les industriels.En ce qui concerne l'analyse des réseaux, l'engouement des années 2000pour les "petits mondes" étudiés pour leurs propriétés globales laisseaujourd'hui de plus en plus de place à des approches rendant àl'individu sa place singulière dans l'espace social. Les grands réseauxsont ainsi une toile de fond qui fournit des outils quantitatifs pourmesurer la grande diversité qualitative des configurations individuelles.Pour illustrer ces démarches, je m'appuierai sur des exemples variésallant de la constitution de l'aristocratie à Buenos Aires sous l'Empireespagnol, jusqu'à la diffusion des url sur Twitter.
Vendredi 17 Janvier
Heure: 00:59 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques remarques d'ordre logique sur la théorie des types homotopiques (2e partie)
Description: Christophe Fouqueré A partir du livre "Homotopy Type Theory", seront abordés les points
suivants: théorie des types (à la Martin-Löf), notions (très)
élémentaires d'homotopie et axiome d'univalence, hiérarchisation des
types et conséquences sur la partie interprétant la logique (en
particulier le tiers-exclus). Nous n'aborderons pas nombre de points
(théorie des catégories, types homotopiques d'ordre supérieur,
reconstruction des réels, ...) hautement intéressants de ce livre.
Mardi 21 Janvier
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Programmation linéaire mixte robuste avec variables de recours continues
Description: Pierre-Louis Poirion Nous
nous intéresserons aux problèmes linéaires mixtes
bi-niveaux, c'est à dire aux problèmes dans lesquels le
processus de décision est divisé en deux parties : dans un
premier temps, les valeurs optimales des variables dites "de
décisions" seront calculées ; puis, une fois que
l'incertitude sur les données est levée, nous calculerons
les valeurs des variables dites "de recours".


Nous
commencerons par résoudre un problème linéaire simplifié
dans lequel l'incertitude porte seulement sur le membre
droit des contraintes, et est modélisée par un polytope bien
particulier. Nous supposerons en outre que le problème
vérifie une propriété dite "de recours complet". Nous
verrons alors une méthode permettant, à partir d'un
programme robuste quelconque, de se ramener à un programme
robuste équivalent dont le problème déterministe associé
vérifie la propriété de recours complet. Avant de traiter le
cas général, nous nous limiterons d'abord au cas où les
variables de décisions sont entières. Nous testerons alors
notre approche sur un problème de production. 

Enfin,
nous nous placerons dans un cadre probabiliste et chercherons
à estimer la pertinence de l'ensemble d'incertitude choisi.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Gaussian expectations in random tensor theory from meanders and stabilized-interval-free permutations
Description: Valentin Bonzom Je m'intéresse à l'espérance de polynômes en des variables aléatoirestensorielles distribuées selon une gaussienne. Je présenteraibrièvement une famille de polynômes dont les espérances comptent desnombres de systèmes de méandres, puis je discuterai en détail cettefamille de méandres. Un méandre étant vu comme un collage de deuxsystèmes d'arches, il s'agit ici de méandres étiquetés par unepermutation qui détermine un système d'arches à partir de l'autre. Jemontrerai que le nombre de méandres étiquetés par une permutationdonnée se décomposent naturellement en méandres irréductibles,étiquetés par des permutations qui ne stabilisent aucun sous-interval(Stabilized-Interval-Free permutations).
Vendredi 24 Janvier
Heure: 00:59 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Proving complexity bounds in linear logic with context semantics
Description: Matthieu Perrinel First, I will present a simplified version of Ugo Dal Lago's context
semantics on proof-nets. Next, I will present abstract properties based on
context semantics which entail complexity bounds. I will use this
properties to make short proofs of strong complexity bounds for ELL and
LLL. Finally, I will sketch how we are currently using context semantics to
give new type systems characterizing Ptime and the first LL-based type
system characterizing primitive recursive functions.
Mardi 28 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatoire et algorithmique dans les classes de permutations
Description: Adeline Pierrot Cet exposé donnera un aperçu du domaine de recherche accessible etdynamique des permutations à motifs exclus, tout en illustrant dans cecadre les interactions fructueuses existantes entre combinatoire etalgorithmique. Un outil clé présenté sera la décomposition parsubstitution des permutations, qui est un exemple de décompositionrécursive d'objets discrets utile tant sur le plan combinatoirequ'algorithmique, et qui fait partie du même cadre général que ladécomposition modulaire des graphes. Une telle décomposition permet demettre en évidence la structure des objets étudiés, et de l'exploiterafin d'obtenir des résultats de nature énumérative, des algorithmes degénération aléatoire, ou des algorithmes de décision.
Mardi 4 Février
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Capacity Planning for Natural Gas Transmission Networks
Description: Jesco Humpola We present a procedure for capacity planning of large-scale real-world
natural gas distribution networks. It decides which combination of
network extensions such as additional pipelines, compressors or valves
should be added to increase the network's capacity or enhance its
operational flexibility. We formulate this as a mixed-integer nonlinear
problem. A sub-problem has different convex reformulations. Hence we use
a combination of linear outer approximation and NLP solution techniques
to solve the MINLP. We show that every dual solution of the convex
reformulations allows to generate capacity inequalities (or cutting
planes) which reduce the overall solution time when added to the
formulation. The dual solution also enables the measurement of
infeasibility level of the scenario. Furthermore we give a primal
heuristic for our model. We present computational results that are
obtained by a special tailored version of the solvers SCIP and IPOPT.
Vendredi 7 Février
Heure: 00:59 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Models of a Non-Associative Composition
Description: Guillaume Munch-Maccagnoni We characterise the
polarised evaluation order through a categorical structure where the
hypothesis that composition is associative is relaxed. Duploid is
the name of the structure, as a reference to Jean-Louis Loday's duplicial
algebras. The main result is a reflection Adj→Dupl where Dupl
is a category of duploids and duploid functors, and Adj is the
category of adjunctions and pseudo maps of adjunctions. The result suggests
that the various biases in denotational semantics:
indirect, call-by-value, call-by-name... are a way of hiding the fact that
composition is not always associative.
Lundi 10 Février
Heure: 00:59 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La paraphrase : approches et modélisations linguistiques, mise en oeuvre informatique
Description: Emmanuel Cartier Les paraphrases et les inférences font l'objet d'une attention
particulière en TAL étant donné les conséquences d'une bonne extraction
/ génération dans nombre d'applications : extraction, systèmes de
questions/réponses, résumé automatique, traduction automatique,
générateurs etc.
La présentation focalisera sur les approches et les modélisations
linguistiques du phénomène, et de leur mise en oeuvre informatique. Elle
pourra servir de ferment de discussion dans le cadre de la campagne
SemEval à venir. 
Mardi 11 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Petit voyage autour des sémantiques quantitatives de la logique linéaire
Description: Michele Pagani Une sémantique dénotationelle interprète les types de données (commeBool ou Int) par des espaces mathématiques (posets, treillis,structures algébriques) et les programmes par des fonctions sur cesespaces. L'intérêt d'une telle interprétation étant de donner unedescription du comportement opérationnel des programmes qui faitabstraction du langage dans lequel les programmes sont écrits.Les sémantiques quantitatives sont en particulier les sémantiquesdénotationelles issues de la logique linéaire, où les types de donnéessont interprétés par des espaces vectoriels (ou, plus généralement,des modules), les programmes qui utilisent exactement une fois leursdonnées d'entrée deviennent des fonctions linéaires (au sensalgébrique), alors que les programmes qui utilisent leurs ressourcesun nombre indéterminé de fois (comme les programmes récursifs ou lesprogrammes utilisant l'instruction while, par exemple) sontinterprétés par des fonctions analytiques, approximables par despolynômes, qui représentent des calculs partiels.Ces sémantiques sont particulièrement naturels pour décrire desprogrammes non-déterministes, voire probabilistes ou quantiques,l'addition exprimant une sorte de superposition des états élémentaireset les scalaires associant une estimation quantitative à une tellesuperposition.Dans cet exposé, je chercherai à donner une intuition del'interprétation des programmes via quelques exemples de sémantiquesquantitatives et à donner un aperçu des résultats récemmentobtenus, en particulier dans le cadre des langages fonctionnelsprobabilistes.
Vendredi 14 Février
Heure: 00:59 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Two Intensional Phenomena: The Size of Church-Rosser Diagrams, and Characterization of PTIME via Overlapping Cons-Free Systems
Description: Jakob Grue Simonsen We will informally discuss two very different problems that both concern
the intensional behaviour of very simple calculi: First-order term
rewriting systems, respectively lambda calculus.

The first problem concerns finding bounds on the size of confluence and
Church-Rosser diagrams: If s is a term in a confluent, we know that
every "peak" t *<-s ->* t' has a corresponding "valley" t ->* s' *<- t',
but it is not at all clear how the number of steps in the "valley" relates
to the number of steps in the "peak" and to the size of the starting
term s. We will discuss how valley sizes can always be computed, how
the sizes may majorize any computable function on the integers, how
exponential bounds can be found for first-order term rewriting, and
for lambda calculus how there is an enormous difference between the
best-known upper bound (not even elementary recursive) and the
worst-case example known (doubly exponential).

The second problem concerns implicit complexity and how to characterize
the set of PTIME-decidable sets by first-order term rewriting systems
in the most liberal fashion possible: No restrictions on reduction
strategy (hence no insistence on call-by-name, call-by-value or other
functional-programming-inspired strategies), no restrictions on overlaps
between left-hand sides of rules, and as few linearity constraints as we
can get away with (and absolutely no explicit typing of any kind).

The talk will be kept at high-level and present the interesting problems
and challenges; we will only delve into technical details if the
audience feels like it. The material presented is based on joint,
ongoing, work with Jeroen Ketema and Daniel de Carvalho.
Mardi 18 Février
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Circuit and bond polytopes in series-parallel graphs
Description: Mathieu Lacroix We describe the circuit polytope in series-parallel graphs. We show the existence of a compact extended formulation for the latter, which inductively provides the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe the bond polytope in series-parallel graphs.This is a joint work with S. Borne, R. Grappe, P. Fouilhoux and P. Pesneau.
Vendredi 21 Février
Heure: 00:59 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Paramétricité et type identité : application à la structure d'ω-groupoide des types
Description: Marc Lasson La paramétricité est un concept introduit par Reynolds afin d'étudier
l'abstraction de type polymorphe du système F. Elle renvoie au
fait que des programmes bien typés ne peuvent ``inspecter le type de leurs
arguments'': ils doivent se comporter uniformément au regard des
types abstraits. Reynolds formalise cette notion en montrant que les
programmes polymorphes du système F satisfont des relations
logiques définies par induction sur la structure des types. Le système de
types sous-jacent à coq est suffisamment expressif pour exprimer
sa propre théorie de la paramétricité. Dans cet exposé, nous nous
intéresserons aux conséquences de cette remarque lorsqu'elle est
appliquée au type des égalités, et nous montrerons en particulier comment
montrer des résultats de paramétricité concernant les espaces de lacet
(loop spaces, en anglais) et en déduire des résultats sur la structure de
groupoide de la théorie des types.
Mardi 25 Février
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Cluster fans
Description: Gleb Koshevoy One of the main motivation of S.Fomin and A.Zelevinskyfor introducing cluster algebras was the desire toprovide a combinatorial framework to understand the structure of ''dualcanonical bases'' in coordinate rings of various algebraic varieties related to semisimple groups. For a finite cluster algebra, they show that the cluster complex can be implemented as a simplical fan in the vector space span by the simple roots of the corresponding Lie algebra. We show that the cluster complex for cluster algebra of the base affine space for GL(n) can be implementedas a simplicial fan in the space span by interval one-column semistandard Young tableaux filled in the alphabet {1,...,n}. For n>6, such a fan contains infinitely many cones and its support covers semistandard Young tableaux corresponding toreal elements of the dual canonical basis. For types ADE, cluster complexes of the corresponding finite cluster algebras aresubfans of our cluster complex with appropriate n's.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A left/right dynamic on permutations
Description: Quentin de Mourgues Soit s une permutation dans Sigma_n.Soit i(s)=s(1), j(s)=s^{-1}(1),Soit C_k le cycle 1>2>...>(k-1)>1 (k,k+1,..,n points fixes).On definit L et R comme suit:L(s) = C_{j(s)}.s etR(s) = s.C_{i(s)}^{-1}Il est facile de voir que L et R sont inversibles, la dynamique L/R partitionne donc Sigma_n en classes d'équivalence qui sont des graphes orientés uniformes (une arête entrant/sortant par "couleur" L et R) fortement connexes.Dans cet exposé, on étudiera ces classes : leur nombre, leur taille, leur structure, etc.
Vendredi 28 Février
Heure: 00:59 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Ludique et types: éléments de déconstruction
Description: Christophe Fouqueré We will discuss/analyze the following observations and the questions they rise:Observations:
- Each formula of MALL2 is denoted by a behaviour in Ludics.
- Cut-elimination is fully plugged into / at the heart of Ludics.
- And with properties expected for a logic.

Questions:
- Can we characterize exactly behaviours that denote MALL(c/2/inf) formulas?
- Can we define the algebraic structure of a behaviour? I.e. a language
for behaviours?
- Can we develop a sequent calculus for this language?
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.