Session 1 
09:0009:05 
Opening: Emo Welzl 
09:0509:25 
Adaptive QuasiNewton Methods
Sebastian Stich, UC de Louvain
(Gremo Sep 15, 2010  Sep 30, 2014)
Abstract:
The BroydenFletcherGoldfarbShanno (BFGS) algorithm is an
iterative method for solving unconstrained optimization
problems. BFGS can be seen as an approximation of Newton's method
that does not need to evaluate the Hessian directly. Instead, the
inverse of the Hessian matrix is approximated using lowrank
updates in every iteration. Both the "optimization" and
"approximation" components of this algorithm influence each
other, which can lead to interesting coupling effects, for example
acceleration.
Whist the acceleration of BFGS has been observed on many practical
problems, it has resisted thorough theoretical analysis. Recent
findings of Gower and Richtárik (2016) shed some new light on
this problem. In this talk I will discuss some recent results.

09:2509:45 
Computing Optimal Feedlinks
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002  Sept 30, 2005)
Abstract:
Given a polygon representing a transportation network together with
a point p in its interior, we aim to extend the network by
inserting a line segment, called feedlink, which connects
p to the boundary of the polygon. Once a feed link is fixed, the
geometric dilation of some point q on the boundary is the ratio
between the length of the shortest path from p to q through the
extended network, and their Euclidean distance. The utility of a
feedlink is inversely proportional to the maximal dilation over
all boundary points.
We give a linear time algorithm for computing the feedlink with
the minimum overall dilation, thus improving upon the previously
known algorithm of complexity O(n log n).
This is joint work with Marko Savić.

09:4510:05 
Cplanarity via Perfect Matching
Radoslav Fulek, IST Austria
Abstract:
We show that cplanarity is solvable in quadratic time for flat
clustered graphs with three clusters, if the combinatorial
embedding of the underlying abstract graph is fixed. In simpler
graphtheoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts
embedded on a 2sphere, our algorithm decides if we can augment
G by adding edges without creating an edgecrossing so that in
the resulting spherical graph the vertices of each part induce a
connected subgraph.

10:0510:25 
Finding Pairwise Intersections Inside a Query Range
Ali D. Mehrabi, TU Eindhoven
(Gremo Nov 14  Dec 16, 2016)
Abstract:
Given a set O of objects in the plane (and in
ℝ^{3}), we study the problem of preprocessing O into
a data structure that allows us to efficiently report all pairs of
objects from O that intersect inside a query range Q.
This is joint work with Mark de Berg and Joachim Gudmundsson,
presented at WADS 2015.

10:2511:00 
Coffee Break 
Session 2 
11:0011:20 
Efficient Stabilization of Cooperative Matching Games
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002  Mar 31, 2005)
Abstract:
Cooperative matching games have drawn much interest partly because
of the connection with bargaining solutions in the networking
environment. However, it is not always guaranteed that a network
under investigation gives rise to a stable bargaining outcome. To
address this issue, we consider a modification process, called
stabilization, that yields a network with stable outcomes, where
the modification should be as small as possible. Therefore, the
problem is cast to a combinatorialoptimization problem in a
graph. Recently, the stabilization by edge removal was shown to be
NPhard. On the contrary, in this paper, we show that other
possible ways of stabilization, namely, edge addition, vertex
removal and vertex addition, are all polynomialtime
solvable. Thus, we obtain a complete complexitytheoretic
classification of the natural four variants of the network
stabilization problem. We further study weighted variants and
prove that the variants for edge addition and vertex removal are
NPhard.
This is joint work with Takehiro Ito, Naonori Kakimura, Naoyuki
Kamiyama, and Yusuke Kobayashi.

11:2011:40 
An Introduction to Complex Oriented Matroids
Katharina Schaar, TU München
(Gremo Aug 15  Sep 25, 2016)
Abstract:
Oriented matroids encode the combinatorics of a real point
configuration. In this talk, we will have a look at the
combinatorics of a complex point configuration. We will examine so
called "phirotopes", that is, complex oriented matroids. (Real)
oriented matroids can be understood as a singularity of
phirotopes. Nevertheless, the theory of phirotopes substantially
differs from the one of oriented matroids. The realizability of
phirotopes, for example, can be determined by evaluating a
polynomial, whereas deciding the realizability of oriented
matroids is known to be NPhard. I will give a short introduction
to phirotopes and illustrate why we are interested in them by
highlighting some surprising properties.

11:4012:00 
CindyJS  Interactive Visualization on Modern Devices
Michael Strobel, TU München
(Gremo Aug 15  Sep 25, 2016)
Abstract:
Visualization and realtime interactive simulation play an
important role both in mathematical research and in mathematical
communication. The CindyJS Project aims at the development of a
software platform and its mathematical foundation that allows a
versatile and fast prototyping of mathematical experiments and
visualizations which can be used for research and
demonstration. The project attacks both the mathematical and the
software related aspects of such a platform. In particular, the
system should be usable as a flexible authoring system for
providing mathematical content that can run in contemporary web
browsers (including mobile devices), taking advantage of modern
hardware and software technologies.
This talk will give an overview about the capabilities of the
software and the challenges we are facing during its development.

12:0012:20 
Incremental construction of convex polyhedra and Voronoi diagrams
Luis Barba, Carleton U / UL Bruxelles
Abstract:
We study the amortized number of combinatorial changes (edge
insertions and removals) needed to update the structure of the
1skeleton of a polyhedron defined as the intersection of a set of
n halfspaces in ℝ^{3} as a new halfspace is
added. To that effect, we define an abstract update operation for
planar graphs that can be used to model the addition of new
halfspaces to the polyhedron. Moreover, this operation can also be
used to model the addition of a new site in several variants of
Voronoi diagrams.
Using this abstraction, we show that the amortized number of edge
insertions and removals needed to maintain the combinatorial
structure of the polyhedron as a new halfspace (or a new site to
the Voronoi diagram) is added is O(√n) amortized. A matching
Ω(√n)
combinatorial lower bound is shown for this abstract
operation. These results provide the first evidence of the
existence of an algorithm to incrementally construct the
intersection of n halfspaces in subquadratic time. Indeed, we
present an algorithm running in O(n^{3/2} polylog n) time
for the special case where the 1skeleton of the polyhedron is
always a tree.
This is join work with Sarah Allen, John Iacono and Stefan
Langerman.

12:2012:25 
Organizational Remarks: Michael Hoffmann 