Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
October 22 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Introduction to Polyhedral Computation
- Speaker:
Komei Fukuda (ETH Zurich)
- Abstract:
Polyhedral computation is a rapidly expanding
field of algorithmic mathematics which addresses the
computational complexity of
solving problems associated with convex polyhedra
and search for efficient algorithms. One of the most
fundamental problems is the vertex enumeration problem
that is to list all vertices of a convex polytope given
as the solution set to a system of m linear inequalities
in d-variables. The problem in its dual form is
the facet enumeration problem (or the convex hull problem)
for a given set of m points in R^d. These problems
of enumerative nature
have the important characteristic: the size of output may be
very large and cannot be polynomially bounded by
the input size in general. Consequently the most natural
question is to ask whether a problem can be solved in
time polynomial in both the input size and the output size.
We shall use the usual term polynomially solvable
if this is the case. (This is consistent with the conventional
use for the decision problems whose output is of constant length.)
In this talk, we review various fundamental problems in
polyhedral computation. The main objectives are to
understand the wealth of the problems investigated
and to present both known results and open problems
on polynomial solvability.
The problems we discuss include the vertex enumeration,
the arrangement/zonotope construction, the Minkowski
addition of polytopes, the Gröbner fan construction
and the parametric LP/LCP.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar