Networks
Training
Training Week 12
On 25 - 29 October 2021 NETWORKS organizes the twelfth Training Week for PhD Students of NETWORKS.
Minicourse "Spanners and coresets for geometric approximation algorithms"
Lecturer: Sándor Kisfaludi-Bak
Abstract: Many algorithmic problems become easier in a geometric setting, and in the past decades several techniques have been put forward to achieve speedups using the geometric structure. Very often however one needs to use some more involved tools to exploit the geometric structure. We will discuss two such prominent tools, geometric spanners and coresets, both of which have proven useful in a variety of algorithmic applications.
Spanners are a way to simplify a dense network into a sparse one while preserving its distance properties approximately. It is natural to study spanners on geometric graphs, where the vertices correspond to points in some metric space, and the length of each edge is the distance of its endpoints. Coresets are a way to simplify objects or point sets in Euclidean space, by finding a small essential subset on which the relevant measure (volume, width, etc.) is approximately preserved.
In this mini-course we will introduce some important spanners and coresets, and see how they can be computed efficiently. In the end we will use them to get geometric approximation algorithms for some variants of the traveling salesman problem.
Minicourse "Phase transitions in random constraint satisfaction problems"
Lecturer: Noela Müller
Abstract: A random constraint satisfaction problem (rCSP) is a problem whose variables are subjected to a number of randomly chosen and possibly conflicting constraints. Problems of this build appear in various disciplines such as combinatorics, theoretical computer science, statistical physics or biology. For example, random k-SAT and random graph coloring are two prominent rCSPs from computer science and combinatorics, respectively. Naturally, several tasks can be associated with problems of this kind: to decide whether there exists a valid assignment of values to the variables that satisfies all the constraints (a solution), to count the number of solutions or to find an assignment that violates the fewest clauses.
In the study of these questions, it has been experimentally observed, conjectured and in increasingly many cases rigorously proven, that as the number of constraints per variable is increased, the nature of the problem at hand does not change gradually, but undergoes several phase transitions. Of these, the most well-known is the satisfiability threshold, below which the rCSP admits a solution with high probability (w.h.p.) and above which there is no solution w.h.p. However, other phase transitions may occur as well, which are connected to the structure of the set of solutions. In the last decades, tools and ideas from statistical physis have been successfully applied to the study of rCSPs, and the insights gained by this approach as well as by a convergence of disciplines has also led to a tremendous progress in a more rigorous understanding of such phase transitions. This minicourse will give an introduction to rCSPs, define random factor graphs as a common framework for them and convey some of the ideas underlying the heuristics from statistical physics that have played a major role in recent mathematical proofs.
Location
Conferentiecentrum De Schildkamp, Leerdamseweg 44, 4147 BM Asperen