Henk Meijer - Queen's University, Kingston, Kanada

Maximum Dispersion and Geometric Maximum Weight Cliques

Abstract: Consider the problem of selecting a set of locations from a set of feasible positions. If we are interested in minimizing interference between the locations, a natural objective function is the maximazation of the average distance between selected points. In this talk we will look at geometric instances of this problem. In particular, we present algorithmic results for the case where the feasible positions are represented by points in d-dimensional space, and distances correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. In the case where the number of locations to be chosen is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where the number of locations to be chosen is part of the input, we present polynomial-time algorithms that approximate an optimal solution with performance ratios arbitrarily close to 1.

Kolloquium - 16 Uhr s.t.

Marc Pfetsch - Technische Universität Berlin

Reconstructing Polyhedra - Part II

Abstract: The vertex-facet incidence matrix of a polytope essentially includes all the information about its combinatorics. For instance, its face lattice can easily be computed from this matrix.
The guideline of this talk is the following question: To what extend can we reconstruct the full combinatorics of an unbounded polyhedron?

1. Given the vertex-facet incidence matrix of an arbitrary polyhedron P, can it be decided whether P is a polytope or an unbounded polyhedron? The answer is "yes" and uses topological methods (Euler characteristic).
2. Given the vertex-facet incidence matrix of an unbounded polyhedron P, can we reconstruct its face-lattice? The answer in general is of course "no", take a cone for example. But even for polyhedra, which satisfy the property that no facet contains the vertex set of another one, the answer is "no". For simple polyhedra the answer is "yes".
3. Given a simple, and simplicial polyhedron P, then P is necessarily a simplex or a polygon. (This generalizes a well-known result about polytopes.)