 |
|
Publications 2001 - 2003
2003
|
Combinatorial generation of small point configurations and hyperplane arrangements
|
|
Authors
|
L. Finschi and K. Fukuda
|
|
Abstract
|
A recent progress on the complete enumeration of oriented matroids enables us to generate all combinatorial types of small point configurations and hyperplane arrangements in general dimension, including degenerate ones. This extends a number of former works which concentrated on the non-degenerate case and are usually limited to dimension 2 or 3. Our initial study on the complete list for small cases has shown its potential in resolving geometric conjectures.
|
|
Download
|
PDF
|
|
An adaptive algorithm for vector partitioning
|
|
Authors
|
K. Fukuda, S. Onn, and V. Rosta
|
|
Abstract
|
The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L) v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.
|
|
Download
|
PS.gz
|
2002
|
Generation of oriented matroids - a graph theoretical approach
|
|
Authors
|
L. Finschi and K. Fukuda
|
|
Abstract
|
Not available
|
|
Download
|
PS.gz
|
|
Pricing American Put Options by Fast Solutions of the Linear Complementary Problem
|
|
Authors
|
Hans-Jakob Lüthi, Artan Borici
|
|
Abstract
|
The value function of an American put option defined in a discrete domain may be given as a solution of a Linear Complementarity Problem (LCP). However, the state of the art methods that solve LCP converge slowly. Recently, Dempster, Hutton \& Richards have proposed a Linear Program (LP) formulation of the American put and a special simplex algorithm that exploits the option structure. They give numerical examples with run times which grow almost linearly with the number of spatialmgrid points.
Based on these ideas we show in a constructive fashion that a new algorithm may be devised which processes the original LCP in linear number of spatial grid points.
|
|
Download
|
PDF
|
|
Almost Disjoint Traingles in 3-Space
|
|
Author
|
Gyula Karolyi
|
|
Abstract
|
Two traingles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Omega(n^(3/2)).
|
|
Download
|
PS, PS.gz
|
|
|
|
2001
|
A Multi-Agent Bidding System For Task Assignment
|
|
Authors
|
Dan Burkolter, Jens Henoch, Eleni Pratsini
|
|
Abstract
|
This study considers a market based approach in task assignment within a shop-floor consisting of several work-cells. As orders/tasks arrive at the shop-floor, they are announced and agents representing the appropriate work-cells bid for the tasks. Each work-cell calculates its bid based on its marginal cost of performing the task and the lowest bid is awarded the task. The costs consist of fixed and variable components as well as costs of deviating from certain operational goals. The risk attitude of the agents as well as various bidding strategies can be applied to the cost model in order to obtain a bid. The bidding system has been implemented in a multi-agent framework. Various bidding models were tested and their performance was compared to those of reference assignment rules. Results indicate that while simple assignment rules perform quite well under stable operating conditions, the bidding model provides a more flexible operation that can respond to uncertain market conditions.
|
|
Reference
|
Proceedings of the Third International World Manufacturing Congress, Rochester, NY, 2001
|
|
Download
|
PDF
|
|
|
|
|
Approximate Analytic Center Quadratic Cut Method For Strongly Monotone Variational Inequalities
|
|
Authors
|
Hans-Jakob Lüthi, Benno Büeler
|
|
Reference
|
Advances in Convex Analysis and Global Optimization. N. Hadjisavvas and P. Pardalos (Eds.), Kluwer Academic Publishers, 2001, pp. 345-360.
|
|
Download
|
PDF
|
|
|
|
|
Computing the Width of a Point Set in 3-Space
|
|
Authors
|
Bernd Gärtner, Thomas Herrmann
|
|
Abstract
|
We present a new algorithm to solve the 3-dimensional width problem, i.e.\to determine two parallel planes of smallest distance such that the region between the two planes contains a given point set. Like the algorithm of Houle and Toussaint, our method has quadratic worst-case complexity but is much faster in practice. In contrast to Houle and Toussaint, we do not use plane sweep or point location techniques; instead, we apply simple methods from linear optimization. The resulting implementation seems to be faster than an existing implementation of Houle and Toussaint's method using the LEDA-library, and it is now part of the Computational Geometry Algorithms Library CGAL.
|
|
Reference
|
Abstracts for the Thirteenth Canadian Conference on Computational Geometry, pages 101-103. University of Waterloo, August 13-15 2001.
|
|
Download
|
PDF, PS, PS.gz
|
|
|
|
|
Agent-Based Simulation Platform for Evaluating Management Concepts
|
|
Authors
|
Jens Henoch, Heinz Ulrich
|
|
Abstract
|
This paper presents an agent-based simulation platform for evaluating management concepts in the domain of logistics. It is based on a discrete event simulator HIDES and extends it by adding a third layer, the management level. This management level comprises a management system including an agent community, where agents are in charge of the operational tasks in the logistics system. The management system is designed according to an adaptation of the Viable System Model. Agents are implemented using the ACTALK framework, a generic actor language.
|
|
Reference
|
Heemink et al., ed., Proceedings of the 4th International Eurosim 2001 Congress, 2001
|
|
Download
|
PDF
|
|
|
|
2000 and earlier
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
