2 Décembre - 8 Décembre


Retour à la vue des calendrier
Mardi 3 Décembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A branch-and-bound method for box constrained integer polynomial optimization
Description: Claudia D'Ambrosio We consider the problem of minimizing an arbitrary polynomial subject to
box and integrality constraints. We propose a new class of
under-estimators composed of separable functions of the original variables
and use it within a branch-and-bound scheme to easily and quickly compute
lower bounds. Computational results on randomly generated instances show
good performance with respect to the ones of different open-source solvers
like Couenne, Gloptipoly , and SCIP.
Moreover, the second part of the talk will be devoted to present a
different perspective on partially separable problems. In particula, an
exact algorithm for mixed integer non-linear programming problems with
separable non-convexities will be presented.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Efficient Algorithms for Dualizing Large-Scale Hypergraphs
Description: Uno Takeaki A hypergraph F is a set family defined on vertex set V.The dual of F is the set of minimal subsets H of V such thatJ cap H
e emptyset for any J in FThe computation of the dual is equivalent to many problems, such asminimal hitting set enumeration of a subset family, minimal set coverenumeration, and the enumeration of hypergraph transversals.In this paper, we introduce a new set system induced by the minimalitycondition of the hitting sets, that enables us to use efficient pruningmethods.We further propose an efficient algorithm for checking the minimality,that enables us to construct time efficient and polynomial spacedualization algorithms.The computational experiments show that our algorithms are quite fasteven for large-scale input for which existing algorithms do notterminate in practical time.
Mercredi 4 Décembre
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A New Approach to String Pattern Mining with Approximate Match
Description: Uno Takeaki Frequent string mining is the problem of finding frequently appearingstrings in a given string database or large text.It has many applications to string data analysis on strings such as texts,word sequences, and genome sequences.The problem becomes difficult if the string patterns are allowed to matchapproximately, i.e., a fixed number of errors leads to an explosionin the number of small solutions, and a fixed ratio of errors violatesthe monotonicity that disables hill climbing algorithms, and thusmakes searching difficult.There would be also a difficulty on the modeling of the problem;simple mathematical definitions would result explosion of the solutions.To solve this difficulty, we go back to the motivations to find frequentstrings, and propose a new method for generating string patternsthat appear in the input string many times.In the method, we first compute the similarity between the stringsin the database, and enumerate clusters generated by similarity.We then compute representative strings for each cluster, and therepresentatives are our frequent strings.Further, by taking majority votes, we extend the obtained representativesto obtain long frequent strings.The computational experiments we performed show the efficiency of bothour model and algorithm; we were able to find many stringpatterns appearing many times in the data, and that were long butnot particularly numerous.The computation time of our method is practically short, such as20 minutes even for a genomic sequence of 100 millions of letters.
Vendredi 6 Décembre
Heure: 00:59 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Data-race freedom by typing in Mezzo
Description: Thibaut Balabonski Mezzo is a typed programming language in the ML family whose static discipline controls aliasing and ownership. This rules out certain mistakes, including representation exposure and data races, and opens up new opportunities, such as gradual initialization or (more generally, and somewhat speculatively) the definition and enforcement of object protocols.

In this talk, I will explain the basic design of Mezzo on examples, and show how its type system inspired by separation logic gives a simple way of tracking ownership of fragments of shared memory between concurrent threads. Beyond the usual claim that "well-typed programs do not go wrong", we guarantee that well-typed Mezzo programs have no data-races.