Combinatorics on Arrangements and Parametric Matroids : A Bridge between Computational Geometry and Combinatorial Optimization(Special Issue on Algorithm Engineering : Surveys)

概要

論文の詳細を見る
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, combinational optimization and computational geometry, through this bridge.
社団法人電子情報通信学会の論文
2000-03-25