Chers collègues,
Vous êtes tous cordialement invités à nous rejoindre le mardi 15 décembre 2015 de 9h30 à 12h00 en salle A009 pour une matinée d’exposés de l’équipe METHODES.
Vous trouverez ci-joint et ci-dessous le planning provisoire des exposés.
- Natalia Kushik: 9h30 – 9h50
Title: Decreasing the complexity of problems in model based testing and quality estimation
Abstract: This presentation is devoted to the study of complexity issues when performing software model based testing and quality estimation. In particular, it is focused on effective utilization of Finite State Machines (FSMs) for this purpose. Due to the fact that most of the related problems are NP- or PSPACE-complete while the length of the corresponding sequences is exponential (or even higher), several ways of decreasing such complexity need to be discussed. The presentation contains original results on using scalable representations as well as defining specific FSM classes for which the worst complexity case cannot be reached. - Guanglei Wang: 9h55 – 10h15
Title: The optimal mapping of cloud virtual machines — recent progress in bilinear optimization
Abstract: One of the challenges of cloud computing is to assign virtual machines to physical severs optimally and efficiently. The aim of cloud operators is to minimize the mapping cost while respecting the location, bandwidth constraints. The resulting formulation appears to be a bilinear 0-1 program. Preliminary convex relaxations and decomposition approaches are employed to solve the problem. Also, motivated by this hard problem, we will review some fundamental results in bilinear optimization. - Aymen Jaziri: 10h20 – 10h40
Title: Traffic Hotspot Localization and Performance Analysis of Heterogeneous Networks under the Presence of Traffic Hotspots
Abstract: Because existing tools do not provide high accuracy for hotspot localization, we were motivated to propose a new method for traffic hotspot localization with an acceptable accuracy. So, based on the combined use of several KPIs (Key Performance Indicators) directly obtained from the O&M and projected over the coverage map, we give a new promising alternative for traffic hotspot localization which achieves acceptable localization along with sufficient precision and significant savings on the cost of localization. After that, when the traffic localization is provided through our proposed method or through those studied in the literature, operators are interested to identify methods that can be implemented in the process of small cell planning in order to obtain the desired performances after their deployment. Consequently, we analytically study the efficiency of deploying small cells in the presence of traffic hotspots and we analyze the impact of imperfect small cell positioning on the performance of HetNet deployments. The objective is to know when the system generates positive offloading gains from deploying a small cell even with errors due to the hotspot localization process and thus in the small cell positioning and also when the deployment of small cells is worthless. From a practical point of view, this study allows to evaluate the gain that can be generated from the deployment of a small cell considering an error of hotspot localization and to identify the hotspot localization errors that can be accepted or tolerated in order to be exploited in operational tasks mainly for HetNet design. So far, this evaluation allows operators investing in an efficient way to retain the appropriate localization tool. - Antoine Glorieux: 10h45 – 11h05
Title: On the most imbalanced orientation of a graph
Abstract: We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by MAXIM . We first characterize graphs for which the optimal objective value of MAXIM is zero. Next we show that MAXIM is generally NP-complete and cannot be approximated within a ratio of 1/2+ε for any constant ε > 0 in polynomial time unless P = NP even if the minimum degree of the graph δ equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to 1/2 . An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments. - Longbiao Chen: 11h10 – 11h30
Title: Prediction of Urban Human Mobility Leveraging Bike Sharing System Open Data
Abstract: The patterns of human movements in urban areas are highly dynamic and complex in both spatio and temporal dimensions. An accuracy prediction of urban human movement can help city managers to prevent traffic congestions and potential security risks. By leveraging the trip data from the widely-deployed bike sharing systems, we attempt to help predict how many people will arrive or leave an area, where they are coming from and going to, and eventually, which areas will become over crowded in the future. We evaluated our work in New York City, and discovered interesting human movement patterns. - Farah Ait Salaht: 11h35 – 11h55
Title: Stochastic bounding models for performance analysis of cloud
Abstract: We propose to evaluate the performance of a cloud node (data center) using hysteresis queueing systems and stochastic bound methods. We represent the dynamic behavior of the cloud node by a hysteresis queueing system with forward and backward threshold vectors. The client requests (or jobs) are represented by bulk arrivals entering the buffer, and executed by Virtual Machines (VMs) which are activated and deactivated according to the occupation of the queue, and the threshold sequences. As the system is quite difficult to analyze, we propose to define different bounding systems « less complex » and easier to study. Two approaches are used, one by aggregating the probability distribution of the batch arrivals and another by taking models with the same sequences of forward and backward thresholds. We show the relevance of the proposed bounding systems by presenting some numerical results for the performance measures of a data center.