Mai 2018


Retour à la vue des calendrier
Mercredi 2 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Discrete convexity and applications to combinatorics and optimization
Description: Gleb Koshevoy I will explain theory convexity for lattices, free Abelian groups without torsion. I will show that a famous class of polytopes, polymatroids of combinatorial optimization, is related to one of classes of discrete convexity. Several instances of discretely convex functions related to combinatorics of Young tableaux will be demonstrated.
Vendredi 11 Mai
Heure: 13:30 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: complexité algébrique III
Description: Paulin
Lundi 14 Mai
Heure: 14:00 - 15:30
Lieu: Salle B407, bâtiment B, Université de Villetaneuse
Résumé: Immerman-Szelepcsenyi
Description: Damiano
Mardi 15 Mai
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Phylogenetic trees modeled by increasing Schröder trees
Description: Mehdi Naima In biology a phylogenetic tree is a classical tool to represent the evolutionary relationship among
species. Our main frustration against the classical combinatorial models is related to the chrono-
logical aspect that seems not considered by the models. E. g. the Schröder trees do not take into
account the time evolution. We develop in this paper a model for phylogenetic trees satisfying
in priority two constraints: (1) to take into account the chronological evolution and (2) to be
efficient to simulate. Our model is based on some increasingly labeling of Schröder trees.
Heure: 12:00 - 13:30
Lieu: Salle A303, bâtiment A, Université de Villetaneuse
Résumé: logique catégorique I
Description: Damiano
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Strong and Cheap SDP and SOCP Hierarchies for Polynomi al Optimization
Description: Bissan Ghaddar In this talk, we propose alternative SDP and SOCP approximation hierarchies to obtain global bounds for general polynomial optimization problems (POP), by using SOS, and SDSOS polynomials to strengthen existing hierarchies for POPs. Specifically, we show that the resulting approximations are substantially more effective in finding solutions of certain POPs for which the more common hierarchies of SDP relaxations are known to perform poorly. Numerical results based on the proposed hierarchies are presented on non-convex instances form the literature as well as on instances from the GLOBAL Library.
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hom-idempotent graphs, normal Cayley graphs and stable Kneser graphs
Description: Mario Valencia Pabon Dans cet exposé, on parlera de la notion de hom-idempotence dans l'ensemble de graphes : un graphe G est dit hom-idempotent s'il existe un homomorphisme entre le graphe produit cartésien G*G et G lui-même. Cette notion est fortement liée à une classe particulière de graphes de Cayley qu'on appelle les graphes de Cayley normaux. On montrera que les graphes de Kneser K(n,k) ne sont pas hom-idempotents. On montrera aussi que les graphes s-stables de Kneser K(n,k)_s ne sont pas hom-idempotents si s=2 mais, pour n=sk+1, K(n,k)_s est hom-idempotent. Finalement, on appliquera la notion de hom-idempotence à la k-tuple coloration de graphes : une k-tuple coloration de graphes consiste en affecter à chaque sommet un k-ensemble de couleurs de sorte que sommets adjacents reçoivent k-ensembles disjoints. On montrera que la différence entre le nombre chromatique du graphe produit cartésien de graphes de Kneser K(n,k)*K(n,k) et le nombre chromatique d'une 2-tuple coloration du même graphe K(n,k)*K(n,k) n'est pas bornée.
Mercredi 23 Mai
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Facteurs premiers de nombres remarquables
Description: Florian Luca Soit une suite de nombres entiers et considérons le produit des n premiers termes. Combien ce produit a-t-il de facteurs premiers ? Quel est le plus grand ? Nous présenterons différents résultats concernant des suites célèbres : les nombres de Fermat, de Fibonacci, ...
Heure: 15:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin Packing Problems
Description: Roberto Baldacci In this work, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, Delorme et al. (2016) proposed 500 new test instances for the 1D-BPP; the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of one hour imposed to each execution of the algorithm.
The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1D-BPP and the subset-row inequalities proposed by Jepsen et al. (2008). We describe an ad-hoc label-setting algorithm to solve the pricing problem, dominance and fathoming rules to speedup its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, like the incompatibility between the items, and therefore we also apply it to solve the 1D-BPP with conflicts (1D-BPPC).
The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods, and successfully closed several open 1D-BPPC instances.
Vendredi 25 Mai
Heure: 14:00 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: type-two polynomial time and restricted lookahead
Description: Florian Steinberg
Mardi 29 Mai
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: (CIP) Discussion on graph rewriting systems (with examples and equations)
Description: Nicolas Behr Séminaire annulé à cause de difficultés de transport. Le séminaire de 14h00
est maintenu.
Heure: 14:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorics of chemical reaction systems
Description: Nicolas Behr Reporting on recent work with G.H.E. Duchamp and K.A. Penson (arXiv:1712.06575), I plan to present a formulation of chemical reaction systems in the so-called stochastic mechanics formalism. This approach allows to uncover some deep relationships between the combinatorial techniques of boson normal-ordering and the dynamics of chemical reaction networks: each semi-linear reaction type induces an evolution within a space of probability distributions that can be computed explicitly via our techniques. For the interesting remaining types of reactions, some results involving systems of Sobolev-Jacobi orthogonal polynomials will be presented.
Jeudi 31 Mai
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Graphes dynamiques - Modélisation et Clustering
Description: Tabea Rebafka To model recurrent interaction events we propose a new dynamic random graph model : an extension of the stochastic block model in continuous time, where every individual (node) belongs to a latent group and interactions (edges) between two individuals are modelled using inhomogeneous Poisson processes. We develop a semiparametric variational expectation-maximization algorithm to estimate model parameters and to perform a clustering of the nodes. We illustrate the performance of our method on real datasets.