MONDAY AUG 1 - STUDENT WORKSHOP
Place: MFF UK, Malostranské náměstí 2/25, 118 00 Praha 1, Czechia
10:00-10:50 Henry Fleischmann
Title: Hardness of Approximation or Steiner Trees in Metric Spaces
Abstract: In this talk we discuss new hardness of approximation bounds for the Hamming and $$l_1$ Steiner tree problems based on a reduction from Vertex Cover. We then discuss progress toward showing APX-hardness of the Euclidean Steiner tree problem for n points in n dimensional space.
11:00-11:50 Tung Anh Vu
Title: Generalized k-Center: Distinguishing Doubling and Highway Dimension
Abstract: We consider generalizations of the k-Center problem in graphs of low doubling and highway dimension. For the Capacitated k-Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are k, the number of outliers and the doubling dimension of the supplier set. On the other hand, we show that for the Capacitated k-Center problem, which is a special case of CkSwO, obtaining a parameterized approximation scheme (PAS) is W[1]-hard when the parameters are k, and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.
11:50-13:00 Lunch break
13:00-13:50 Gaurav Kucheriya
Title: Edge-ordered graphs with almost linear extremal functions
Abstract: The central theme of Turán type graph problems is to maximize the number of edges a graph can have, under certain (forbidding) conditions, which is known as its extremal function. Here we consider graphs with edge-order, that is, the edges are linearly ordered. A paper by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos and Vizer started the study of these type of extremal problems for edge-ordered variant.
Since the extremal function for unordered graphs follows a dichotomy: the function is linear if and only if the forbidden graph is forest. So similar dichotomy was conjectured for edge-ordered and vertex-ordered graphs. Here, I present the solution that settles it in the former case, which is joint work with Gabor Tardos.
14:00-15:30 Lawrence Frolov
Title: On the unique existence of Jello
Abstract: The days of spring, will surely bring, the birds and bees cavorting. But since I am a gentleman, I’d much rather be proving the well posedness of differential equations. In this talk we do precisely that, prove the existence of unique solutions for a wide range of differential equations which frequently appear in the study of physics. By the end of the talk, we hope to prove the well-posedness of Jello, which is modeled via an infinite system of point particles which are coupled by springs.
TUESDAY AUGUST 2
Morning: possible visit of MCW or work on problems
14:00 - 16:00 Jiri Fink
Title: Exact and heuristic algorithms for Steiner tree problem
Abstract: We will discuss various approaches to obtain solutions for Steiner tree problem. Exact algorithms based on Integer linear programming provide optimal solutions for small graphs. For larger graph, feasible solutions can be obtain using simple greedy rules which can be improved using various local search methods or evolutionary algorithms.
WEDNESDAY AUGUST 3
Morning: possible visit of MCW or work on problems
14:00 - 16:00 Vahideh Keikha
Title: Polygon Inclusion Problem
Abstract: In this lecture, we discuss the polygon containment problem and the basic geometric properties and data structures for this problem. We study classic algorithms and their failures on general variants besides novel methods to solve this problem in high dimensions.
THURSDAY AUGUST 4
Morning: possible visit of MCW or work on problems
14:00 - 16:00 Martin Loebl
Title: Optimisation by Enumeration
Abstract: We discuss a curiour way how to efficiently solve the Max Cut problem on 2-dimensional surfaces.
