IEICE Trans - Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization

Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization

Takeshi TOKUYAMA

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.362-371
Publication Date: 2000/03/25
Online ISSN:
DOI:
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Matroids and Related Discrete Systems
Keyword:
parametric optimization,  computational geometry,  combinatorics,  matroids,

Full Text: PDF(303.5KB)>>

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.