 |
|
Publications 2004
IFOR Mitteilungen
This booklet informs about ongoing projects and future events at the IFOR and appears once at the end of the year.
› read more
|
From the zonotope construction to the Minkowski
addition of convex
polytopes
|
|
Author
|
Komei
Fukuda
|
|
Abstract
|
A
zonotope is the Minkowski addition of line segments in
Rd. The zonotope construction problem is to
list all extreme points of a zonotope given by its line segments. By
duality, it is equivalent to the arrangement construction problem that
is to generate all regions of an arrangement of
hyperplanes.
By replacing line segments with convex
V-polytopes, we obtain a natural generalization of the zonotope
construction problem: the construction of the Minkowski addition of
k polytopes. Gritzmann and Sturmfels studied this general
problem in various aspects and presented polynomial algorithms for the
problem when one of the parameters k or d is fixed.
The main objective of the present work is to introduce an efficient
algorithm for variable d and k. Here we call an
algorithm efficient or polynomial if it runs in time
bounded by a polynomial function of both the input size and the output
size. The algorithm is a natural extension of a known algorithm for
the zonotope construction, based on linear programming and reverse
search. It is compact, highly parallelizable and very easy to
implement.
This work has been motivated by the use of
polyhedral computation for optimal tolerance determination in
mechanical
engineering.
|
|
Reference
|
Journal of Symbolic Computation (38):1261-1272, 2004
|
|
Download
|
PDF
|
|
The Criss-Cross Method Can Take Omega(n^d) Pivots
|
|
Authors
|
K. Fukuda and B. Kaluzny
|
|
Abstract
|
Using deformed products of arrangements, we construct a family of linear programs with n inequalities in Rd on which, in the worst-case, the least-index criss-cross method requires Omega(nd) (for fixed d) pivots to reach optimality.
|
|
Reference
|
Proc. 20th Annu. ACM Sympos. Comput. Geom., ACM Press, New York, 401-408, 2004
|
|
Evaluating Market Attractiveness: Individual Incentives vs. Industry
Profitability
|
|
Authors
|
H. Dawid and M. Reimann
|
|
Reference
|
Computational Economics
|
|
A Variable Neighborhood Search for the Multi Depot Vehicle Routing
Problem with Time Windows
|
|
Authors
|
K. Doerner, R. F. Hartl, M. Polacek, and M. Reimann
|
|
Reference
|
Journal of Heuristics
|
Technical Reports / Preprints
|
A non-regular Gröbner fan
|
|
Author
|
Anders
Jensen
|
|
Abstract
|
The
Groebner fan of an ideal I\subset k[x_1,...,x_n],
defined by Mora and Robbiano, is a complex of polyhedral cones in
Rn. The maximal cones of the fan are in bijection with
the distinct monomial initial ideals of I as the term order
varies. If I is homogeneous the Groebner fan is complete and
is the normal fan of the state polytope of I. In general the
Groebner fan is not complete and therefore not the normal fan of a
polytope. We may ask if the restricted Groebner fan, a subdivision of
Rn>=0, is regular i.e. the normal fan of a
polyhedron. The main result of this paper is an example of an ideal in
Q[x_1,...,x_4] whose restricted Groebner fan is not
regular.
|
|
Download
|
PS arxiv.org
|
|
Primal-dual algorithms for data depth
|
|
Authors
|
D. Bremner, K. Fukuda, and V. Rosta
|
|
Abstract
|
The halfspace depth of a point p relative to a data set S in d-dimension is the smallest number of data observations from S in any closed halfspace containing p. A point with largest depth was considered as the generalization of the median of S by Tukey. The computation of the halfspace depth of a point is equivalent to the closed hemisphere problem, which was shown to be NP-complete by Johnson and Preparata. We propose primal--dual algorithms that update both an upper bound and a lower bound of the depth and terminate as soon as the two bounds coincide. We report preliminary computational experiments.
|
|
Download
|
PDF
|
|
Lecture notes on oriented matroids and geometric computation
|
|
Author
|
Komei Fukuda
|
|
Reference
|
Lecture notes on oriented matroids and geometric computation. Technical Report
Swiss Federal Institute of Technology, Lausanne and Zurich, 2004
|
|
Download
|
Handouts
|
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
