Session 1 
08:5509:00 
Opening: Emo Welzl 
09:0009:20 
Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002  Mar 31, 2005)
Abstract:
We propose a new combinatorial optimization problem that we call
the submodular reassignment problem. We are given k submodular
functions over the same ground set, and we want to find a set that
minimizes the sum of the distances to the sets of minimizers of
all functions. The problem is motivated by a twostage stochastic
optimization problem with recourse summarized as follows. We are
given two tasks to be processed and want to assign a set of
workers to maximize the sum of profits. However, we do not know
the value functions exactly, but only know a finite number of
possible scenarios. Our goal is to determine the firststage
allocation of workers to minimize the expected number of
reallocated workers after a scenario is realized at the second
stage. This problem can be modeled by the submodular reassignment
problem.
We prove that the submodular reassignment problem can be solved in
strongly polynomial time via submodular function minimization. We
further provide a maximumflow formulation of the problem that
enables us to solve the problem without using a general submodular
function minimization algorithm, and more efficiently both in
theory and in practice. In our algorithm, we make use of
Birkhoff's representation theorem for distributive lattices.
This is joint work with Naoyuki Kamiyama, Naonori Kakimura and
Yusuke Kobayashi.

09:2009:40 
A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs
Bettina Speckmann, TU Eindhoven
(Gremo Oct 1, 2001  May 31, 2003)
Abstract:
We say that an algorithm is stable if small changes in the input
result in small changes in the output. This kind of algorithm
stability is particularly relevant when analyzing and visualizing
timevarying data. Stability in general plays an important role in
a wide variety of areas, such as numerical analysis, machine
learning, and topology, but is poorly understood in the context of
(combinatorial) algorithms. We present a framework for analyzing
the stability of algorithms and focus in particular on the
tradeoff between the stability of an algorithm and the quality of
the solution it computes. Our framework allows for three types of
stability analysis with increasing degrees of complexity: event
stability, topological stability, and Lipschitz stability. We
demonstrate the use of our stability framework by applying it to
kinetic Euclidean minimum spanning trees.
This is joint work with Wouter Meulemans, Kevin Verbeek, und Jules
Wulms.

09:4010:00 
On the Optimality of the Uniform Random Strategy
Tibor Szabó, FU Berlin
(Gremo Sep 1, 2000  Aug 31, 2008)
Abstract:
The concept of biased MakerBreaker games, introduced by Chvátal
and Erdős, is a central topic in the field of positional games,
with deep connections to the theory of random structures. For any
given hypergraph ℋ the main questions is to determine
the smallest bias q(ℋ) that allows Breaker to force
that Maker ends up with an independent set of ℋ. In the
talk we discuss recent joint work with Chris Kusch, Juanjo Rue, and
Christoph Spiegel, about matching general winning criteria for
Maker and Breaker when the game hypergraph satisfies a couple of
natural “containertype” regularity conditions about the degree
of subsets of its vertices. These enable us to derive a hypergraph
generalization of the ℋbuilding games, studied for
graphs by Bednarska and Łuczak. Furthermore, we investigate the
biased version of generalizations of the van der Waerden games
introduced by Beck. We refer to these generalizations as Rado games
and determine their threshold bias up to constant factor by
applying our general criteria. We find it quite remarkable that a
purely game theoretic deterministic approach provides the right
order of magnitude for such a wide variety of hypergraphs, when the
generalizations to hypergraphs in the analogous setup of sparse
random discrete structures are usually quite
challenging.

10:0010:20 
From a (p,2)Theorem m to a Tight (p,q)Theorem
Shakhar Smorodinsky, Ben Gurion U
(Gremo Feb 15, 2004  Oct 31, 2004)
Abstract:
Say that a family of sets satisfy the (p,q)property for some
fixed integers P ≥ q ≥ 2 if out of every p members some
q have a nonempty intersection. Wegner and (independently)
Dol'nikov (almost 50 years ago) used a (p,2)theorem for
axisparallel rectangles to prove the following tight
(p,q)theorem for q>√2p: If a family of axisparallel
rectangles in the plane satisfy the (p,q)property, then the
family can be pierced by pq+1 points. It is easily seen that
the value pq+1 is best possible for any family satisfying the
(p,q)property. These were the only values of q (in the range
q>√2p ) that such a tight bound on the piercing number was
known.
In this talk we present a general method which allows using a
(p,2)theorem as a bootstrapping to obtain a tight
(p,q)theorem, for families with Helly number 2, even without
assuming that the sets in the family are convex or compact. To
demonstrate the strength of this method, we obtain an improvement
of Wegner and Dol'nikov's result. Namely, we show that the bound
pq+1 above holds for all q ≥ 7 log p (compared to
q ≥ √2p
of Wegner and Dol'nikov).
This is joint work with Chaya Keller.

10:2010:40 
Coffee Break 
Session 2 
10:4011:00 
Planar 3SAT with a Clause/Variable Cycle
Alexander Pilz, TU Graz
(Gremo Feb 1, 2016  March 31, 2018)
Abstract:
In the Planar 3SAT problem, we are given a 3SAT formula together
with its incidence graph, which is planar, and are asked whether
this formula is satisfiable. Since Lichtenstein's proof that this
problem is NPcomplete, it has been used as a starting point for a
large number of reductions. In the course of this research,
different restrictions on the incidence graph of the formula have
been devised, for which the problem also remains hard.
We investigate the restriction in which we require that the
incidence graph is augmented by the edges of a Hamiltonian cycle
that first passes through all variables and then through all
clauses, in a way that the resulting graph is still planar. The
problem of deciding satisfiability of a 3SAT formula turns out to
remain NPcomplete even if the incidence graph is restricted in
that way and the Hamiltonian cycle is given. This complements
previous results demanding cycles only through either the variables
or clauses. In contrast to that, some other restricted versions of
planar 3SAT turn out to be always satisfiable.

11:0011:20 
The Z_{2}Genus of Kuratowski Minors
Radoslav Fulek, IST Austria
Abstract:
A drawing of a graph on a surface is independently even if every
pair of nonadjacent edges in the drawing crosses an even number of
times. The Z_{2}genus of a graph G is the minimum g such that
G has an independently even drawing on the orientable surface of
genus g. An unpublished result by Robertson and Seymour implies
that for every t, every graph of sufficiently large genus
contains as a minor a projective (t x t)grid or one of the
following socalled tKuratowski graphs: K_{3,t}, or t
copies of K_{5} or K_{3,3} sharing at most two common
vertices. We show that the Z_{2}genus of graphs in these families
is unbounded in t; in fact, equal to their genus. Together, this
implies that the genus of a graph is bounded from above by a
function of its Z_{2}genus, solving a problem posed by Schaefer
and Štefankovič, and giving an approximate version of the
Hanani–Tutte theorem on orientable surfaces.
This is joint work with Jan Kynčl.

11:2011:40 
On Open Problems Related to the ErdősSzekeres Theorem
Pavel Valtr, Charles U Prague
Abstract:
Background to several open problems related to the ErdősSzekeres
(Happy Ending) Theorem will be outlined. The open problems include
the following questions in ℝ^{3}:
 For a given k>0, what is
the minimum integer n>0 such that every set of n points in
general position in ℝ^{3} contains k convexly independent
points. In particular, does n=n(k) grow exponentially with k?
 Is there a positive integer n such that any set P of n
points in general position in ℝ^{3} contains an 8hole, that is,
a set of 8 convexly independent points such that the interior of
their convex hull contains no point of P?

11:4012:00 
SemiRandom Graph Process
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002  Sept 30, 2005)
Abstract:
We introduce and study a novel semirandom graph process, described
as follows. The process starts with an empty graph on n
vertices. In every round of the process, one vertex v of the graph
is picked uniformly at random and independently of all previous
rounds. We then choose an additional vertex (according to a
strategy of our choice) and connect it by an edge to v.
For various natural monotone increasing graph properties P, we
give tight upper and lower bounds on the minimum (extended over the
set of all possible strategies) number of rounds required by the
process to obtain, with high probability, a graph that satisfies
P. Along the way, we show that the process is general enough to
approximate (using suitable strategies) several wellstudied random
graph models.
This is joint work with Omri BenEliezer, Dan Hefetz, Gal
Kronenberg, Olaf Parczyk and Clara Shikhelman.

12:0012:05 
Organizational Remarks: Michael Hoffmann 