Monday, January 18, 2010
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Location problems play a central role in Operations Research. In
center location problems the location of one or more facilities
has to be found such that the longest distance from a facility to
a customer assigned to this facility is as small as possible. In
the following we deal with a graph model for the 1-center problem.
Let a connected graph $G=(V,E)$ with vertex set $V$ and edge set
$E$ be given. We view the vertices of $G$ as customers. Every edge
$e$ in $G$ has a positive length $\ell(e)$. The \emph{absolute
1-center problem} asks for a point $s$ in $G$ which may be a
vertex or may lie on an edge, such that the longest distance from
point $s$ to a vertex $v$ is as small as possible. Handler showed
that in a tree the midpoint of a longest path is an absolute
1-center and this is uniquely determined. The \emph{vertex
1-center problem} asks for a vertex $s$ such that the longest
distance from vertex $s$ to any other vertex is as small as
possible. It can be shown that in a tree the closest vertex to the
absolute 1-center is a vertex 1-center.
In an \emph{inverse 1-center location problem} on graph $G$ the
point $s$ is given and the task is to change the lengths of edges
in $G$ such that $s$ becomes a 1-center. Every length change
incurs some cost. We are looking for a solution of the inverse
problem where the (weighted) sum of cost is minimum. Cai, Yang and
Zhang proved that the inverse $1$-center location problem with
edge length modifications on general unweighted directed graphs is
$ \cal NP $-hard. Recently, Yang and Zhang proposed an $O(n^2 \log
n)$ time solution method for the inverse \emph{vertex} 1-center
problem on an unweighted tree provided that the modified edge
lengths always remain positive. Dropping this condition, they
mention that the general problem can be solved in $O(n^3 \log n)$
time. Their method is based on linear programming arguments. We
outline combinatorial methods for solving the inverse absolute
1-center problem as well as the inverse 1-vertex center problem in
$O(n^2)$-time provided no edge length is reduced to 0. In the case
of essential topology changes we develop algorithms of $O(n^2r)$
time complexity, where $r$ is the compressed depth of the tree.
This improves on the bound of Yang and Zhang. An improved running
time of $O(n \log n)$ can be obtained in the case of uniform cost
for changing edge lengths.
Colloquium - 16:00
Abstract:
Parameterized complexity aims to design exact algorithms whose running times
depend on certain parameters of the input data that are naturally
related to
the problem at hand and in a way capture its complexity. A problem is
called fixed-parameter tractable (FPT) with respect to a parameter k if
there is an efficient algorithm to solve the problem for the cases where
the
parameter k is small. Another objective of this theory is to show that
such
algorithms are unlikely to exist for certain problems (and parameters).
Not many geometric problems have been studied from the parameterized
complexity point of view. Most research has focused on special
(combinatorial) parameters for geometric problems, like, e.g., the
number of
inner points (i.e., points in the interior of the convex hull) for the
TSP
problem or for the problem of computing minimum convex decompositions.
Also,
on the negative side, only few connections between geometric problems
and
known hard parameterized problems are known to date. We provide a brief
tour
of results from parameterized complexity theory for various geometric
problems (e.g. hyperplane depth, clustering) with a focus on the
dimension
as the parameter. Our results indicate that all these problems are
inherently difficult in higher dimensions.