¿Qué tan fundamentales son los matroides y los greedoides en el diseño de algoritmos?

Inicialmente, matroides se introdujeron generalizar las nociones de independencia lineal de una colección de subconjuntos sobre algún motivo previsto . Ciertos problemas que contienen esta estructura permiten que los codiciosos algoritmos encuentren soluciones óptimas. El concepto de greedoids se introdujo más tarde para generalizar esta estructura para capturar más problemas que permitan encontrar soluciones óptimas mediante métodos ambiciosos. $E$ $I$

¿Con qué frecuencia surgen estas estructuras en el diseño de algoritmos?

Además, la mayoría de las veces un algoritmo codicioso no podrá capturar por completo lo que es necesario para encontrar soluciones óptimas, pero aún puede encontrar soluciones aproximadas muy buenas (Bin Packing, por ejemplo). Dado eso, ¿hay alguna manera de medir qué tan "cercano" está un problema a un greedoid o matroid?

algorithms optimization combinatorics greedy-algorithms matroids Nicholas Mancuso
fuente

Respuestas:

Es difícil responder la pregunta "con qué frecuencia". Pero como con todas las "estructuras subyacentes", el beneficio proviene de reconocer que el problema subyacente que uno está tratando de resolver tiene una estructura matroide (o greedoide). No se trata solo de problemas matroides. El problema de la intersección matroide tiene un modelo específico (coincidencia bipartita).

Nick Harvey realizó su tesis doctoral recientemente sobre algoritmos para problemas de matroides y también analizó la optimización de la función submodular (que generaliza los problemas de matroides). Leer la introducción y los antecedentes de la tesis puede ser útil.

Suresh
fuente

Solo quiero agregar una nota sobre "cercanía". Si un algoritmo codicioso da una aproximación k, el problema puede estructurarse como un k-matroide.

Nicholas Mancuso

+1. Buena respuesta. Me pregunto por qué la tesis dice que una función submodular es una generalización o resumen de un matroide. La única conexión que puedo encontrar entre los dos es el rango de un submatroide en un subconjunto es una función submodular.

Tim

Hay una conexión geométrica muy elegante. Para comprender esto mejor, debe consultar en.wikipedia.org/wiki/Polymatroid . Aproximadamente, si el politopo asociado con una función submodular tiene propiedades específicas, entonces obtienes un matroide. Para más información sobre esto, vea el libro de Satoru Fujishige: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html

Suresh

Como se indica en CLRS (página 437 de la 3ª edición), la teoría matroide no cubre el problema de selección de actividad y el problema de codificación de Huffman. ¿La teoría greedoide los cubre?

hengxin