Welcome to the web page of the junior seminar of the LIPN

Here you can find every information about past and future seminars - room B107

#### 15th junior seminar: 23/02/2018, 15:30

Désirée Rigonat (DecisionBrain): "Optimising a large scale bike sharing system: the London experience".
The London Cycle Hire Scheme (LCHS), managed by Serco Group Plc, is one of the largest bike sharing schemes in the world, with 815 stations and over 13,000 bikes. Due to the size and utilisation rate of the system, Serco faces a major challenge in ensuring adequate supply of bikes at all locations at all times. Furthermore, the Transport for London (TfL), which oversees the LCHS, has very strict service commitments, KPI targets and associated financial penalties. To optimize the mamagement of such a large scheme, DecisionBrain designed and provided a decision support tool called the Distribution Planning Optimization (DPO) System. DPO operates 24hours a day and tackles several complex problems: forecasting the demand for bikes and docking points, finding the best inventory levels for all stations at any given time so that demand is satisfied, building a schedule for Serco operators that are employed in bike redistribution in order to reach the said best inventory levels at stations and finally building a schedule for operators in charge of repairs and maintenance. In this talk, we will illustrate how the aforementioned problems have been tackled and the solving algorithms that have been developed. Thanks to DPO, Serco is now able to consistently meet the service levels required by TfL and has improved the overall quality and availability of the service, as reported by both the Serco LCHS Operations team and actual LCHS utilisation data.

#### 14th junior seminar: 12/12/2018, 15:30

Thi Thanh Huyen Nguyen (LoVe): "Quasi optimal model checking for concurrent systems".
A dynamic partial order reduction (DPOR) algorithm is optimal when it always explores at most one representative per Mazurkiewicz trace. Existing literature suggests that the reduction obtained by the non-optimal, state-of-the-art Source-DPOR (SDPOR) algorithm is comparable to optimal DPOR. We show the first program with O(n) Mazurkiewicz traces where SDPOR explores O(2^n) redundant schedules. We furthermore identify the cause of this blow-up as an NP-hard problem. Our main contribution is a new approach, called Quasi-Optimal POR, that can arbitrarily approximate an optimal exploration using a provided constant k. We also present parallelization of our QPOR to speed up the exploration using parallel resources. We also present an implementation of our method in a new tool called Dpu using specialised data structures. Experiments with Dpu, including Debian packages, show that optimality is achieved with low values of k, outperforming state-of-the-art tools.

#### 13th junior seminar: 22/10/2018, 15:30

This meeting in particular will be an opportunity to know each other and to introduce ourselves. There will be a short talk from Emiliano (representative of the PhD students in the Board of the Lab - "Conseil de labo") on important infos about thesis and laboratory committee, and the presentation of the junior seminar guidelines. We will be open to suggestions in order to improve the junior seminars.

#### 12th junior seminar: 21/06/2018, 15:30

Emiliano Lancini (AOC): "Box-Total Dual Integrality and k-Edge Connectivity".
The concept of total dual integrality dates back to the works of Edmonds, Giles and Pulleyblank in the late 70's, and is strongly connected to min-max relations in combinatorial optimization. In this work we show a characterization of series-parallel graphs in terms of box-total dual integrality of the k-edge-connected spanning subgraph polyhedron. The system ${A}x\ge b$ is totally dual integral (TDI) if, for each integer vector c for which $\min \{c x:Ax\ge b\}$ is finite, there exists an integer optimal solution of $\max \{yb:yA = c,\, y \ge0\}$ such that: $$\min \{c x:Ax\ge b\} = \max \{yb:yA=c, \,y \ge0\}.$$ It is known that every integer polyhedron can be described by a TDI system $Ax\ge b$ with $A$ and $b$ integer. The integrality of the TDI system is desirable because, then we have a min-max relation between combinatorial objects. We are interested in the stronger property of box-TDIness. A system $A x\ge b$ is called box-TDI if the system $Ax\ge b, \ell\le x \le u$ is TDI for all rational vectors $\ell$ and $u$. A polyhedron that can be described by box-TDI system is called a box-TDI polyhedron. This definition is motivated by the fact that any TDI system describing a box-TDI polyhedron is box-TDI. The past few years, this property has received a renewed interest and several new box-TDI systems were discovered. We prove that, for $k\ge2$, the k-edge-connected spanning subgraph polyhedron is a box-TDI polyhedron if and only if the graph is series-parallel. Moreover, in this case, we provide a box-TDI system with integer coefficients describing this polyhedron.

#### 11th junior seminar: 17/05/2018, 14:30

Mathias Ramparison (LoVe): "Timed automata with parametric updates".
Timed automata (TAs) represent a powerful formalism to model and verify systems where concurrency is mixed with hard timing constraints. However, they can seem limited when dealing with uncertain or unknown timing constants. Several parametric extensions were proposed in the literature, and the vast majority of them leads to the undecidability of the EF-emptiness problem: “is the set of valuations for which a given location is reachable empty?” Here, we study an extension of TAs where clocks can be updated to a parameter. While the EF- emptiness problem is undecidable for rational-valued parameters, it becomes PSPACE-complete for integer-valued parameters. In addition, exact synthesis of the parameter valuations set can be achieved. We also extend these two results to the EF-universality (“are all valuations such that a given location is reachable?”), AF-emptiness (“is the set of valuations for which a given location is unavoidable empty?”) and AF-universality (“are all valuations such that a given location is unavoidable?”) problems.

#### 10th junior seminar: 15/05/2018, 15:30 room A303

Issam Falih (A3): "Attributed Networks Clustering: Application to recommender systems".
Au cours de la dernière décennie, les graphes se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l'analyse des réseaux complexes. La majeure partie des travaux dans ce domaine s'intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d'attributs associé aux nœuds et/ou aux liens. Ces réseaux sont dites : "réseaux attribués".
Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, nous nous sommes intéressés dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplexe est un modèle de graphe multi-relationnel qui est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans ces travaux, nous menons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Ensuite, nous proposons une nouvelle approche centrée graine pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplexe. Puis, nous présentons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et la structure topologique du réseau. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale.

#### 9th junior seminar: 22/02/2018, 15:30

Tsinjo Rakotoarimalala (CALIN): "Recherche approchée de motif dans un texte".
On appelle boule de rayon k et de centre un mot u l'ensemble de tous les mots à distance inférieure ou égale à k. On s'intéresse dans l'exposé à la distance d'édition appelée aussi distance de Levenshtein. Quelle est la taille de cette boule pour un mot de longueur m ? Cette question nous intéresse pour en déduire la borne inférieure de la complexité en nombre de caractères lus de la recherche approché de motif dans un texte dans des certaines conditions.

#### 8th junior seminar: 13/12/2017, 14:30

Xin YE (LoVe - formerly LCR): "Reachability Analysis of self modifying codes".
Self modifying code is code that modifies its own instructions during execution time. It is nowadays widely used, especially in malware to make the code hard to analyse and to detect by anti-viruses. Thus, the analysis of such self modifying programs is a big challenge. Push-down systems (PDSs) is a natural model that is extensively used for the analysis of sequential programs because they allow to accurately model procedure calls and mimic the program’s stack. In this work, we propose to extend the PushDown System model with self-modifying rules. We call the new model Self-Modifying PushDown System (SM-PDS). A SM-PDS is a PDS that can modify its own set of transitions during execution. We show how SM-PDSs can be used to naturally represent self-modifying programs and provide efficient algorithms to compute the backward and forward reachable configurations of SM-PDSs. We implemented our techniques in a tool and obtained encouraging results. In particular, we successfully applied our tool for the detection of self- modifying malware.

#### 7th junior seminar: 19/10/2017, 14:00

First junior seminar of the year 2017-2018: presentation of the junior seminar to new PhD students

• Alice Pavaux (LCR): "Linear logic"
• Massinissa Hamidi (A3): "Apprendre à partir des exemples et des modèles du domaine - Cas des objets connectés"

#### 6th junior seminar: 21/06/2017, 15:00

Tsinjo Rakotoarimalala (CALIN): "La borne optimale de la recherche de plusieurs motifs dans un texte aléatoire".
En 1977, Andrew C. Yao dans "the complexity of pattern matching on random string" montre que toutes les occurrences de la plupart des motifs de longueur m se cherchent en $(n/m) ln(m)$ dans un texte aléatoire de longueur n. Nous généralisons la preuve de Yao 1977 pour des dictionnaires composés de plusieurs motifs. L'idée est d'encadrer la complexité de l'algorithme optimal inconnu d'un coté on généralise un algorithme de Frédriksson et Grabrowski pour la borne supérieure et de l'autre coté on simplifie le problème et on généralise la méthode de Yao pour la borne inférieure. Le résultat principal est de montrer que la compexité de l'algorithme optimal est en $\theta ( n (\max (ln( s r_m m) /m + \frac{1}{s m_{min}} )))$ où $r_m$ est le nombre de motifs de longueur m dans le dictionnaire et $m_{min}$ est la longueur de plus court motif du dictionnaire.

#### 5th junior seminar: 07/06/2017, 15:00

Emiliano Lancini (AOC): "Multicuts in series parallel graphs and Box-TDIness".
summary (pdf)

#### 4th junior seminar: 17/05/2017, 15:00

Antoine Kaszczyc (LCR): "Typer les acteurs Akka".
Akka est un cadriciel de programmation concurrente. Il est composé d'entités appelés acteurs qui s'envoient des messages. Mon travail consiste à apporter des vérifications statiques aux programmes utilisant Akka. La technique utilisée est un typage assez simple utilisant un graphe. La propriété vérifiée est la possibilité de traitement de tout message envoyé.

#### Third junior seminar: 29/03/2017, 15:00

Imad Kissami (AOC): "High Performance Computational Fluid Dynamics on Clusters and Clouds".
In order to run computational fluid dynamics (CFD) codes on large scale infrastructures, parallel computing has to be used because of the computational intensive nature of the problems. in this paper we investigate the adapt platform where we couple flow partial differential equationsand a poisson equation. This leads to a linear system which we solve using direct methods. The implementation deals with the mumps parallel multi-frontal direct solver and mesh partitioning methods using METIS to improve the performance of the framework. We also investigate, in this paper, how the mesh partitioning methods are able to optimize the mesh cell distribution for the adapt solver.

#### Second junior seminar: 15/02/2017, 15:00

Enrico Bettiol (AOC): "Simplicial Decomposition for Large-Scale Quadratic Convex Programming"
keywords: minimisation of convex function, large scale, simplex, simplicial decomposition, pricing function

#### First junior seminar: 01/02/2017, 13:30

Presentation of the junior seminar, quick presentations (5 min) of subjects of thesis by PhD students of all teams.

• LANCINI Emiliano (AOC): "Dual integrality of conditions for flow problems"
keywords: integer linear programming, discrete optimisation, resolution of simplex algorithm
• RAKOTONARIVO Rado (CALIN): "Random sampling of integer polytops"
keywords: convex hull, polytops, linear programming problem, combinatorial generation
• NGUYEN Hoang Gia (LCR): "Efficient Parametric Verification of Real-Time Systems"
keywords: parametric timed automata, parameter synthesis, decidability, accessibility
• RAKOTOARIMALALA Tsinjo (CALIN): "Recherche de borne optimale pour recherche de motif dans un texte en complixité moyenne"
keywords: complexité moyenne en temps, esperance, recherche de motif dans un texte, borne optimale
• BECK Gael (A3): "Clustering, vizualisation and concepts"
keywords: distributed algorithm, well formed cluster, represent efficiently datas, attraction process, convex hull, locality sensitive hashing

© LIPN 2019 | Mentions légales