Dans quelle mesure les matroïdes et les grédoides sont-ils fondamentaux dans la conception d'algorithmes?

Dans un premier temps , matroïdes ont été introduites pour généraliser les notions d'indépendance linéaire d'une collection de sous - ensembles sur un terrain mis . Certains problèmes qui contiennent cette structure permettent aux algorithmes gourmands de trouver des solutions optimales. Le concept de greedoids a été introduit plus tard pour généraliser cette structure afin de capturer plus de problèmes qui permettent de trouver des solutions optimales par des méthodes gourmandes. $E$ $I$

À quelle fréquence ces structures apparaissent-elles dans la conception d'algorithmes?

En outre, le plus souvent, un algorithme gourmand ne sera pas en mesure de capturer entièrement ce qui est nécessaire pour trouver des solutions optimales, mais peut toujours trouver de très bonnes solutions approximatives (Bin Packing, par exemple). Compte tenu de cela, existe-t-il un moyen de mesurer à quel point un problème est proche d'un greedoid ou d'un matroid?

algorithms optimization combinatorics greedy-algorithms matroids Nicholas Mancuso
la source

Réponses:

Il est difficile de répondre à la question "à quelle fréquence". Mais comme pour toutes les "structures sous-jacentes", l'avantage est de reconnaître que le problème sous-jacent que l'on essaie de résoudre a une structure matroïde (ou greedoid). Ce ne sont pas seulement des problèmes matroïdes. Le problème d'intersection matroïde a un modèle spécifique (appariement bipartite).

Nick Harvey a fait sa thèse de doctorat assez récemment sur les algorithmes pour les problèmes matroïdes et a également examiné l'optimisation de la fonction sous-modulaire (qui généralise les problèmes matroïdes). La lecture de l'introduction et du contexte de la thèse pourrait être utile.

Suresh
la source

Je veux juste ajouter une note concernant la "proximité". Si un algorithme gourmand donne une approximation k, le problème peut être structuré comme un k-matroid.

Nicholas Mancuso

+1. Bonne réponse. Je me demande pourquoi la thèse dit qu'une fonction sous-modulaire est une généralisation ou un résumé d'un matroïde? La seule connexion que je peux trouver entre les deux est le rang d'un sous-droïde sur un sous-ensemble est une fonction submodulaire.

Tim

Il y a une connexion géométrique très élégante. Pour mieux comprendre cela, vous devriez consulter en.wikipedia.org/wiki/Polymatroid . En gros, si le polytope associé à une fonction sous-modulaire a des propriétés spécifiques, vous obtenez un matroïde. Pour plus d'informations à ce sujet, voir le livre de Satoru Fujishige: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html

Suresh

Comme indiqué dans CLRS (page 437 de la 3ème édition), la théorie des matroïdes ne couvre pas le problème de sélection d'activité et le problème de codage de Huffman. La théorie du greedoid les couvre-t-elle?

hengxin