
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization
Takeshi TOKUYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E83D
No.3
pp.362371 Publication Date: 2000/03/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: INVITED SURVEY PAPER Category: Algorithms for Matroids and Related Discrete Systems Keyword: parametric optimization, computational geometry, combinatorics, matroids,
Full Text: PDF>>
Summary:
Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.

