La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization Combinatoire sur les arrangements et les matroïdes paramétriques : un pont entre la géométrie computationnelle et l'optimisation combinatoire

Takeshi TOKUYAMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

É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.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.362-371
Date de publication
2000/03/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
INVITED SURVEY PAPER
Catégories
Algorithmes pour les matroïdes et les systèmes discrets associés

Auteurs

Mots-clés

Table des matières