Session 1 |
09:25-09:30 |
Opening: Emo Welzl |
09:30-09:50 |
A Picture-Hanging Puzzle
Radoslav Fulek, IST Austria
Abstract:
In the picture-hanging puzzle we are to hang a picture so
that the string loops around n nails and the removal of any nail
results in a fall of the picture. We show that the length of a
sequence representing an element in the free group with n
generators that corresponds to a solution of the picture-hanging
puzzle must be at least n2√
log2n.
In other words, this is a lower bound on the length of a sequence
representing a non-trivial element in the free group with n
generators such that if we replace any of the generators by the
identity the sequence becomes trivial. |
09:50-10:10 |
The Art Gallery Problem is ∃R-complete
Tillmann Miltzow, UL Bruxelles
(Gremo May 1 - June 30, 2013)
Abstract:
We prove that the art gallery problem is equivalent under
polynomial time reductions to deciding whether a system of
polynomial equations over the real numbers has a solution.
The art gallery problem is a classical problem in computational
geometry, introduced in 1973 by Viktor Klee. Given a simple polygon
P and an integer k, the goal is to decide if there exists a set G
of k guards within P such that every point p ∈ P is
seen by at least one guard g ∈ G. Each guard corresponds to a
point in the polygon P, and we say that a guard g sees a
point p if the line segment pg is contained in P.
The art gallery problem has stimulated a myriad of research in
geometry and in algorithms. However, despite extensive research,
the complexity status of the art gallery problem has not been
resolved. It has long been known that the problem is NP-hard, but
no one has been able to show that it lies in NP. Recently, the
computational geometry community became more aware of the
complexity class ∃R. The class ∃R consists of problems
that can be reduced in polynomial time to the problem of deciding
whether a system of polynomial equations with integer coefficients
and any number of real variables has a solution. It can be easily
seen that NP ⊆ ∃R.
We prove that the art gallery problem is
∃R-complete, implying that (1) any system of
polynomial equations over the real numbers can be encoded as an
instance of the art gallery problem, and (2) the art gallery
problem is not in the complexity class NP unless
NP=∃R.
As a corollary of our construction, we prove that for any real
algebraic number α there is an instance of the art gallery
problem where one of the coordinates of the guards equals α
in any guard set of minimum cardinality.
That rules out many geometric approaches to the problem.
This is joint work with Mikkel Abrahamsen and Anna
Adamaszek.
|
10:10-10:30 |
Tight Approximability of the Server
Allocation Problem for Real-Time Applications
Yoshio Okamoto, UEC Tokyo
(Gremo Apr 1, 2002 - Mar 31, 2005)
Abstract:
The server allocation problem is a facility location problem for a
distributed processing scheme on a real-time network. In this
problem, we are given a set of users and a set of servers. Then,
we consider the following communication process between users and
servers. First a user sends his/her request to the nearest
server. After receiving all the requests from users, the servers
share the requests. A user will then receive the data processed
from the nearest server. The goal of this problem is to choose a
subset of servers so that the total delay of the above process is
minimized. We prove the following approximability and
inapproximability results. We first show that the server
allocation problem has no polynomial-time approximation algorithm
unless P = NP. However, assuming that the delays satisfy the
triangle inequality, we design a polynomial-time 3/2-approximation
algorithm. When we assume the triangle inequality only among
servers, we propose a polynomial-time 2-approximation
algorithm. Both of the algorithms are tight in the sense that we
cannot obtain better polynomial-time approximation algorithms
unless P = NP. Furthermore, we evaluate the practical performance
of our algorithms through computational experiments, and show that
our algorithms scale better and produce comparable solutions than
the previously proposed method based on integer linear
programming.
This is joint work with Takehiro Ito, Naonori Kakimura, Naoyuki
Kamiyama, Yusuke Kobayashi, and Taichi Shiitada.
|
10:30-11:00 |
Coffee Break |
Session 2 |
11:00-11:20 |
Computing Representative Networks for Braided Rivers
Bettina Speckmann, TU Eindhoven
(Gremo Oct 1, 2001 - May 31, 2003)
Abstract:
Drainage networks on terrains have been studied extensively from
an algorithmic perspective. However, in drainage networks water
flow cannot bifurcate and hence they do not model braided rivers
(multiple channels which split and join, separated by sediment
bars). We initiate the algorithmic study of braided rivers by
employing the descending quasi Morse-Smale complex on the river
bed (a polyhedral terrain), and extending it with a certain
ordering of bars from the one river bank to the other. This allows
us to compute a graph that models a representative channel
network, consisting of lowest paths. To ensure that channels in
this network are sufficiently different we define a sand function
that represents the volume of sediment separating them. We show
that in general the problem of computing a maximum network of
non-crossing channels which are δ-different from each other
(as measured by the sand function) is NP-hard. However, using our
ordering between the river banks, we can compute a maximum
δ-different network that respects this order in polynomial
time. We implemented our approach and applied it to simulated and
real-world braided rivers.
This is joint work with Maarten Kleinhans, Marc van Kreveld, Tim
Ophelders, Willem Sonke, and Kevin Verbeek.
|
11:20-11:40 |
Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs
Csaba Dávid Tóth, CSU Northridge
(Gremo Mar 1, 2000 - Aug 31, 2002)
Abstract:
We consider edge insertion and deletion operations that increase
the connectivity of a given planar straight-line graph (PSLG),
while minimizing the total edge length of the output. We show that
every connected PSLG G=(V,E) in general position can be augmented
to a 2-connected PSLG (V,E ∪ E+) by adding new
edges of total Euclidean length |E+| ≤ 2|E|, and
this bound is the best possible. An optimal edge set E+
can be computed in O(|V|4) time; however the problem
becomes NP-hard when G is disconnected. Further, there is a
sequence of edge insertions and deletions that transforms a
connected PSLG G=(V,E) into a plane cycle G'=(V,E') such that |E'|
≤ 2|MST(V)|, and the graph remains connected with edge length
below |E|+|MST(V)| at all stages. These bounds are the best
possible.
This is joint work with H. Akitaya, R. Inkulu, T. Nichols,
D. Souvaine, and C. Winston.
|
11:40-12:00 |
Making Hamiltonian cycles on small graphs
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002 - Sept 30, 2005)
Abstract:
In 1982, Papaioannou posed the question of finding the smallest
integer n such that Maker wins the unbiased Maker-Breaker
Hamiltonicity game played on edges of Kn, conjecturing
it to be n=8. Our goal is to first introduce this problem in more
detail, with its history and connections to related positional
games. Then we show how we can settle Papaioannou's conjecture in
affirmative, along with some of the implications.
This is joint work with Nikola Trkulja.
|
12:00-12:05 |
Organizational Remarks: Michael Hoffmann |