Professor David Avis
Department of
Communications
and Computer Engineering
School of Informatics
Kyoto University
Yoshida-honmachi 36-1, Sakyo-ku, Kyoto 606-8501, Japan
TEL: 075-753-5953
FAX: 075-753-5972
Email avis@i.kyoto-u.ac.jp
Office: Engineering Building No. 10, room 342
access
map
cv short cv
Online
publications
lrs
Vertex Enumeration/Convex Hull package Reverse
search: applications,
implementations,
tutorial,
demo
My courses:
Introduction
to Algorithms and
Informatics
Computational
Intractability
Polyhedral
Computation
Tohoku course
Geometric Computation Group
Geometric structures, especially high dimensional polyhedra, have
become essential components of models in many areas of engineering
and
science. Applications arise in such diverse areas as bio-mechanics,
chemistry, embedded systems, game theory, physics, robotics,
scheduling
and wireless networks. They are also at the heart of discrete
optimization, particularly linear and integer programming. Related
computational problems are computationally hard, and many important
practical problems are currently out of reach with present
technology.
Our goal is to create new theoretical methods for geometric
computation
and to implement them in efficient, easily usable software for
end-users. Research in this group is divided into three areas.
Research Topics
1. Polyhedral Computation.
We continue the development of the lrs library. This freely
distributed
and widely used code employs the reverse search technique and exact
arithmetic to compute the vertices or faces of high dimensional
polyhedra. New theoretical advances will be needed to improve its
performance on the highly symmetric and degenerate combinatorial
polytopes often found in practice. We also work with current
users of the software to develop additional features and new
applications.
2. Discrete Optimization.
Problems in discrete optimization abound, with such well known
examples
as the travelling salesman problem, vehicle routing problems,
scheduling problems, etc. The most promising general purpose
approach
to solving these kinds of problems is integer programming, and in
particular, the branch-and-cut framework. Success with applying
these
methods often depends on a thorough study of the underlying
polyhedral
model using tools from polyhedral computation. We will look at
specific
new application areas for these techniques, as well as more
fundamental
questions on the complexity of the underlying computations.
3. Quantum Information.
The scale of future integrated circuity made the study of related
quantum effects inevitable. As an exciting by-product the field of
quantum information was born. This extends information theory to
explore the additional communication power available by using
quantum
objects, such as entangled photons. Correlations between
observations
is at the very heart of this exciting area. Polyhedral models can
completely describe correlations obtained by classical experiments,
but
quantum correlations require new geometric structures. We
investigate
the power of quantum information using tools from polyhedral
computation and discrete optimization, especially semi-definite
programming.
My McGill web page