The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Étant donné un problème combinatoire sur un ensemble d'éléments pondérés, si l'on modifie le poids à l'aide d'un paramètre, on obtient une version paramétrique du problème, qui est souvent utilisée comme outil pour résoudre des problèmes de programmation mathématique. Une question intéressante est de savoir comment décrire et analyser la trajectoire de la solution. Si nous considérons la trajectoire de chaque fonction de poids comme une courbe dans un plan, nous avons un ensemble de courbes issues de l’instance du problème. Les courbes induit un complexe cellulaire appelé un arrangement, qui est une cible de recherche populaire en géométrie computationnelle. En particulier, pour la version paramétrique du problème du calcul de la base de poids minimum d'un matroïde ou d'un polymatroïde, la trajectoire de la solution devient un sous-complexe dans un arrangement. Nous introduisons l'interaction entre les deux domaines de recherche, l'optimisation combinatoire et la géométrie computationnelle, à travers ce pont.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Takeshi TOKUYAMA, "Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 362-371, March 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_362/_p
Copier
@ARTICLE{e83-d_3_362,
author={Takeshi TOKUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization},
year={2000},
volume={E83-D},
number={3},
pages={362-371},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copier
TY - JOUR
TI - Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization
T2 - IEICE TRANSACTIONS on Information
SP - 362
EP - 371
AU - Takeshi TOKUYAMA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - 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.
ER -