Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

The Upcoming Monday Lecture and Colloquium

Monday, January 18, 2010

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005

Lecture - 14:15

Rainer E. Burkard - TU Graz

Inverse center location problems

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

Christian Knauer - FU Berlin

The curse of dimensionality (somewhat) explained

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.

Letzte Aktualisierung: 06.01.2010