Mardi 18 Avril
Heure: 
12:30  13:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Deriving differential approximation results for kCSPs from combinatorial designs 
Description: 
Sophie Toulouse Given two integers q, k ? 2, kCSP?q is the unconstrained optimization problem in which variables have domain Z_q and the goal is to optimize a weighted sum of constraints, each acting on at most k of the variables. Standard inapproximability results for MaxkCSP?q often involve balanced kwise independent distributions over Z_q or rather equivalently, orthogonal arrays of strength k over Z_q. We here illustrate how combinatorial designs are a relevant tool in order to establish approximation results for kCSP?q with respect to the differential approximation measure, which compares the distance between the approximate value and the worst solution value to the instance diameter. First, connecting the average differential ratio to orthogonal arrays, we deduce that this ratio is ?(1/n^(k/2)) when q = 2, ?(1/n^(k1)) when q is a prime power and 1/q^k on (k+1)partite instances. We also consider pairs of arrays that can be viewed as some constrained decomposition of balanced kwise independent functions. We exhibit such pairs that allow when q > k to reduce kCSP?q to kCSP?k with an expansion 1/(q?k/2)^k on the approximation guarantee. This implies together with the result of [Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), pp. 141160] a lower approximability bound of 0.429/(q ? 1)^2 for 2CSP?q. Similar designs also allow to establish that every Hamming ball with radius k provides a ?(1/n^k)approximation of the instance diameter. 
Heure: 
14:00  17:00 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Holonomie et nonholonomie des marches dans le quart de plan 
Description: 
Thomas Dreyfus 
Vendredi 21 Avril
Heure: 
15:00  16:30 
Lieu: 
Salle B107, bâtiment B, Université de Villetaneuse 
Résumé: 
Complex network analysis in ubiquitous and social environments 
Description: 
Martin Atzmueller In the world of today, a variety of interaction data of humans, services and systems is generated, e.g. , by sensors and social media. This enables the observation and capture of physical and social activities, and subsequent extended analysis of interactions, structures and patterns covering both online and offline contexts. This talk focuses on behavioral analytics in social media and the physical world, and presents exemplary methods and results in the context of realworld systems. Specifically, we focus on the grounding and analysis of behavior, interactions and complex structures emerging from heterogeneous data, and according modeling approaches using complex network analysis. 

