Tag: networks

Proper vertex coloring with odd occurence - Probabilistic approach

-- Qiancheng Ouyang (LISN)

summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints. A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors. For a graph G, the chromatic number χ(G) is ...

Some results on directed coloring

-- Thomas Bellitto (LIP6, Sorbonne University)

summary: Proper coloring of undirected graphs lies among the most studied problems in graph theory. It asks to color vertices while giving different colors to adjacent ones.
In 1982, Neumann-Lara introduced a generalization of this problem to directed graphs. When walking in an undirected graph, an undirected edge between two ...

Density of sphere packings: from coins to oranges

-- Daria Pchelina (LIPN, Université Paris 13)

summary: How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the "cannonball" packing is an optimal way to do it. This conjecture took almost 400 years to prove and the proof of Hales and Ferguson consists of 6 papers and ...

An introduction to twin-width in graphs via the study of highly inapproximable problems

-- Pierre Bergé (ISIMA, Université Clermont Auvergne)

summary: The goal of this seminar is to introduce the graph parameter "twin-width", defined by Bonnet et al. in 2020. The collection of graphs with bounded twin-width generalizes many well-known families of graphs : planar, bounded treewidth and cliquewidth, unit interval,... The first motivation behind this parameter was that FO-expressible NP-hard ...

TracInAD: Measuring Influence for Anomaly Detection

-- Hugo Thimonier (LISN, Galac)

summary: As with many other tasks, neural networks prove very effective for anomaly detection purposes. However, very few deep-learning models are suited for detecting anomalies on tabular datasets. This talk proposes a novel methodology to flag anomalies based on TracIn, an influence measure initially introduced for explicability purposes. The proposed ...

Introduction à l'apprentissage par renforcement

-- Marc Velay (LISN, Galac)

summary: Cet exposé proposera une introduction à l'apprentissage par renfocement, en présentant les fonctions à maximiser et les types d'approches employées. La présentation suivra l'évolution historique du domaine, du Q-Learning au Deep Reinforcement Learning, en passant par des travaux étant devenus populaires tel que AlphaGo. Nous conclurons ...

Optimal curing policy for epidemic spreading over a community network with heterogeneous population

-- Francesco De Pellegrini (University of Avignon)

summary: The design of an efficient curing policy, able to stem an epidemic process at an affordable cost, has to account for the structure of the population contact network supporting the contagious process. Thus, we tackle the problem of allocating recovery resources among the population, at the lowest cost possible ...

Economics of Age of Information (AoI) Management: Pricing and Competition

-- Lingjie Duan (GALAC, LRI)

Summary: Fueled by the rapid development of communication networks and sensors in portable devices, today many mobile users are invited by content providers to sense and send back real-time useful information (e.g., traffic observations and sensor data) to keep the freshness of the online platforms’ content updates. However, due ...

Self-Stabilization and Byzantine Tolerance for Maximal Matching

-- Laurence Pilard (GALAC, LRI)

Summary: We analyse the impact of transient and Byzantine faults on the construction of a maximal matching in a general network. In particular, we consider the self-stabilizing algorithm called AnonyMatch presented by Cohen et al. in PPL'2016 for computing such a matching. Since self-stabilization is transient fault tolerant, we ...

A Two-level Auction for Resource Allocation in Multi-tenant C-RAN

-- Mira Morcos (GALAC, LRI)

Summary: Next generation (5G) mobile networks are targeting twenty five-fold data rates provided by the current generation of mobile networks, with higher efficiency, enhanced mobility support and seamless management of connected devices. In order to provide such features, at reduced Capital Expenditure (CAPEX) and Operational Expenditure (OPEX), the Cloud- RAN ...