Guillaume Ducoffe is the recipient of an accessit to the PhD prize Graphes “Charles Delorme” 2017 for his PhD thesis entitled Metric properties of large graphs. Congratulations !
The prize will be announced during the next Journées Graphes et Algorithmes — Bordeaux, November 15-17, 2017.
The paper Energy Efficient Content Distribution [1] won the Wilkes Award 2017 (The Wilkes Award is given once a year to the authors of the best paper published in the volume of The Computer Journal from the previous year)
Congratulation to the authors!
@article{araujo:hal-01238051,
TITLE = {{Energy Efficient Content Distribution}},
AUTHOR = {Araujo, J and Giroire, Fr{\'e}d{\'e}ric and Moulierac, J and Liu, Yi and Modrzejewski, R},
URL = {https://hal.inria.fr/hal-01238051},
JOURNAL = {{The Computer Journal}},
PUBLISHER = {{Oxford University Press (UK)}},
VOLUME = {59},
NUMBER = {2},
PAGES = {192-207},
YEAR = {2016},
MONTH = Feb,
DOI = {10.1093/comjnl/bxv095},
KEYWORDS = {Energy Efficiency ; Integer Linear Programming ; Content Deliv-ery Network ; In-network Caching ; Future Internet},
PDF = {https://hal.inria.fr/hal-01238051/file/compj.pdf},
HAL_ID = {hal-01238051},
HAL_VERSION = {v1},
}
GreenDays@Sophia: “Efficacité énergétique dans les Réseaux Filaires et Mobiles, des FAI aux Centres de Données : Challenges & Opportunités”
17th Journées Combinatoire et Algorithmes du Littoral Méditerranéen (JCALM)
Participez aux Journées non thématiques RESCOM 2017 (12-13 janvier 2017) et à la journée thématique RESCOM Communication dans la ville intelligente (11 janvier 2017). Ces évènements sont organisés dans l’amphi Kahn de Inria Sophia Antipolis – Méditerranée et dans la salle E+131 de Polytech sur le Campus SophiaTech.
Le programme et les informations pratiques sont disponibles sur la page des journées.
Abstract: Large scale communication networks are everywhere, ranging from data centers with millions of servers to social networks with billions of users. This thesis is devoted to the fine-grained complexity analysis of combinatorial problems on these networks.
In the first part, we focus on the embeddability of communication networks to tree topologies. This property has been shown to be crucial in the understanding of some aspects of network traffic (such as congestion). More precisely, we study the computational complexity of Gromov hyperbolicity and of tree decomposition parameters in graphs – including treelength and treebreadth. On the way, we give new bounds on these parameters in several graph classes of interest, some of them being used in the design of data center interconnection networks. The main result in this part is a relationship between treelength and treewidth: another well-studied graph parameter, that gives a unifying view of treelikeness in graphs and has algorithmic applications. This part borrows from graph theory and recent techniques in complexity theory.
The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analyzing information flows in these networks, represented as dynamical processes on graphs. First, a coloring game on graphs is studied as a solution concept for the dynamic of communities. We give a fine-grained complexity analysis for computing Nash and strong Nash equilibria in this game, thereby answering open questions from the literature. On the way, we propose new directions in algorithmic game theory and parallel complexity, using coloring games as a case example. Finally, we introduce a new learning problem that is motivated by the need for users to uncover any misuse of their personal data online. We give positive and negative results on the tractability of this problem.
All the publications at the core of this thesis are available online here
Keywords: Graph theory, Hyperbolicity, tree-decomposition, complexity, privacy.
Abstract: The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.
Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.
The team composed of Nathann Cohen (CNRS, LRI, Paris XI) and David Coudert won the Flinders Hamiltonian Cycle Problem (FHCP) Challenge organized by the Flinders Hamiltonian Cycle Project (Flinders University, Adelaide, Australia).
The challenge consisted in solving 1001 instances of the Hamiltonian Cycle Problem over a one year period (September 30 2015 till September 30 2016). The FHCP Challenge Set is a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528 vertices, with an average size of just over 3000 vertices.
We were able to solve 985 instances!
Fatima Zahra Moataz is the recipient of an accessit to the PhD prize Graphes “Charles Delorme” 2016 for her PhD thesis entitled Towards Efficient and Fault-Tolerant Optical Networks: Complexity and Algorithms. Congratulations !
The prize will be announced during the next Journées Graphes et Algorithmes — Paris, November 17, 2016.
Abstract: We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems.
The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and vertex or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths.
The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used.
Finally, we present in the appendix another problem that has been studied during this thesis. It is a graph-theoretic problem referred to as minimum size tree-decomposition and it deals with the decomposition of graphs in a tree-like manner with the objective of minimizing the size of the tree.
Keywords: Asymmetric nodes, forbidden transitions, shared risk link group, routing and spectrum assignment, tree-decomposition, complexity.
