4th workshop of the Center for Foundations of Modern Computer Science

4. workshop Centra základů moderní informatiky

The fourth workshop of the Center for Foundations of Modern Computer Science took place on Monday and Tuesday December 9 and 10, 2019, at Šámalova chata at Nová Louka in Jizerské hory as a part of HOMONOLO 2019.

Abstracts

Martin Koutecký: Bribery, Diffusion, and Social Networks

My research has lead me from researching existing integer programming tools to applying them (and developing new ones) to the problem of bribery. Having resolved some problems there I got interested in the combination of opinion diffusion and bribery, and, more generally, realistic models of campaigning. This leads to several questions about (real) social networks and opinion diffusion in them, such as: are we mostly influenced by those who are like or unlike us? and, do we change opinions gradually or dramatically? These research directions appear so far surprisingly unexplored.

Martin Balko: Holes and islands in random points sets

For a positive integer d, let S be a finite set of points in R^d with no d+1 points on a common hyperplane. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. A set I of k points from S is a k-island in S if the intersection of conv (I) with S is exactly I.

For fixed positive integers d, k and a convex body K in R^d with d-dimensional Lebesgue measure 1, let S be a set of n points chosen uniformly and independently at random from K. We show that the expected number of k-islands in S is in O(n^d). In the case k=d+1, our result shows that the expected number of (d+1)-holes in S is at most 2^{d-1} * d! * (n choose d). Our results improve and generalize several previously known bounds.

This is a joint work with Pavel Valtr and Manfred Schecher.

Andreas Emil Feldmann: Travelling on Graphs with Small Highway Dimension

We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter roughly measures how many central nodes are visited by all shortest paths of a certain length. It has been argued that transportation networks, on which TSP and STP naturally occur for various applications in logistics, typically have a small highway dimension. While it was previously shown that these problems admit a quasi-polynomial time approximation scheme (QPTAS) on graphs of constant highway dimension, we demonstrate that a significant improvement is possible in the special case when the highway dimension is 1. Specifically, we present a fully-polynomial time approximation scheme (FPTAS). We also prove that both TSP and STP are weakly NP-hard for these restricted graphs.

This is joint work with Yann Disser, Max Klimm, and Jochen Könemann