¿Es posible demostrar que, para un problema dado, no existen algoritmos codiciosos óptimos?

Codicioso es un término no formal, pero podría ser (no estoy seguro, es por eso que estoy preguntando) que para ciertos problemas, la codicia puede formularse matemáticamente y así probarse que no existe un algoritmo codicioso óptimo. es posible?

Lo más simple sería configurar el algoritmo codicioso para el problema y luego buscar un contraejemplo. Si encuentra uno, tiene su respuesta. De lo contrario, hay muchas formas de demostrar que la avaricia funciona . Hay algunos problemas con esto, por supuesto (como la forma específica de formular el algoritmo codicioso). En cuanto a caracterizar qué problemas pueden y qué problemas no pueden resolverse con avidez, también hay una respuesta general a eso.

De hecho, en su artículo "Una caracterización exacta de las estructuras codiciosas" ( SIAM J. Discrete Math . 6 , pp. 274-283), Helman, Moret y Shapiro dieron una descripción formal de esto (llamado incrustación matroide , que generaliza tanto matroides como greedoides). Del resumen: "Los autores presentan caracterizaciones exactas de estructuras en las que el algoritmo codicioso produce soluciones óptimas".

En general, el algoritmo codicioso se puede formular en términos de sistemas de conjuntos ponderados . Tiene un conjunto E (por ejemplo, los bordes, en el caso de árboles de expansión mínima), y tiene un conjunto F ⊆ 2 $(E,\mathcal{F},w)$$E$$\mathcal{F}\subseteq 2^E$ de subconjuntos de (piense en bosques de expansión parcial, para el problema de árboles de expansión mínima). F representa las soluciones parciales válidos construidos mediante la combinación de elementos de E . También está la función de peso, w , que le da el peso o el costo de cualquier elemento en $E$$\mathcal{F}$$E$$w$$\mathcal{F}$. Por lo general, suponemos que esto es lineal, es decir, cada elemento en tiene un peso, y los pesos de las soluciones (parciales) son solo la suma de los pesos de los elementos. (Por ejemplo, el peso de un árbol de expansión es la suma de sus pesos de borde). En este contexto, Helman et al. demostró que los siguientes son equivalentes:$E$

1. Para cada función objetivo lineal, tiene una base óptima.$(E,\mathcal{F})$

2. es una incrustación matroide.$(E,\mathcal{F})$

3. Para cada función objetivo lineal, las bases codiciosas de son exactamente sus bases óptimas.$(E,\mathcal{F})$

En otras palabras: para estructuras como estas (que básicamente encarnan el tipo de estructuras generalmente pensadas cuando se trabaja con avaricia), exactamente el conjunto de incrustaciones matroides se puede resolver con avidez.

La definición de una incrustación matroide no es tan difícil, por lo que probar que un problema dado es o no incrustar matroide es ciertamente factible. La entrada de Wikipedia da la definición con bastante claridad. (Comprender la prueba de por qué estas son las estructuras exactas que pueden ser resueltas por la codicia, eso es algo completamente diferente ...)

Si su problema se puede formular en términos de selección de un sistema conjunto ponderada con una función objetivo lineal, y si se puede demostrar que es no una incrustación matroide, entonces usted ha demostrado que no puede ser resuelto con avidez, incluso si no lo has' No he podido encontrar un contraejemplo. (Aunque sospecho que encontrar un contraejemplo sería bastante más fácil).

Este enfoque no está completamente exento de problemas, supongo. Como usted dice, la idea general de la codicia es bastante informal, y bien podría ser posible modificarla de tal manera que no se aplique el formalismo de los sistemas de conjuntos ponderados linealmente.

Sí, hay tal trabajo. Allan Borodin con sus coautores desarrolló una teoría en la que formalizan la noción de codicia y obtienen resultados con los cuales se pueden alcanzar proporciones de aproximación. Presentan una clase de algoritmos de prioridad, que generaliza los algoritmos codiciosos. Su primer trabajo sobre este tema es el documento " Algoritmos de prioridad (incremental) ".

PD El párrafo anterior responde a una pregunta diferente: ¿Es posible demostrar que, para un problema dado, no existen algoritmos codiciosos con una relación de aproximación menor que alguna $1+\epsilon$

Para ivotron: si no quisiste decir mi primera interpretación, eliminaré esta respuesta.

Vea esto también: http://en.wikipedia.org/wiki/Greedoid