É possível provar que, para um determinado problema, não existem algoritmos gananciosos ideais?

Ganância é um termo não formal, mas pode ser (não tenho certeza, é por isso que estou perguntando) que, para certos problemas, a ganância possa ser formulada matematicamente e, assim, seja provado que não existe um algoritmo ganancioso ideal. Isso é possível?

A coisa mais simples a fazer seria configurar o algoritmo ganancioso para o problema e, em seguida, procurar um contra-exemplo. Se você encontrar um, terá sua resposta. Caso contrário, existem muitas maneiras de provar que a ganância funciona . Há alguns problemas com isso, é claro (como a formulação específica do algoritmo ganancioso). Quanto à caracterização de quais problemas podem e quais não podem ser resolvidos com avidez, também existe uma resposta geral.

De fato, em seu artigo “Uma Caracterização Exata de Estruturas Gananciosas” ( SIAM J. Discrete Math . 6 , pp. 274-283), Helman, Moret e Shapiro fizeram uma descrição formal disso (denominada incorporação matróide , que generaliza matroids e greedoids). Do resumo: "Os autores apresentam caracterizações exatas das estruturas nas quais o algoritmo ganancioso produz soluções ótimas".

Em geral, o algoritmo ganancioso pode ser formulado em termos de sistemas de conjuntos ponderados . Você tem um conjunto (por exemplo, as arestas, no caso de árvores abrangentes mínimas) e um conjunto de subconjuntos (pense em florestas abrangentes parciais, para o problema de árvores de abrangência mínima). representa as soluções parciais válidos construídos através da combinação de elementos de . Há também a função de peso, , que fornece o peso ou o custo de qualquer elemento em . Geralmente assumimos que isso é linear - ou seja, cada elemento emE F ⊆ 2 E E F E w F$(E,\mathcal{F},w)$$E$$\mathcal{F}\subseteq 2^E$$E$$\mathcal{F}$$E$$w$$\mathcal{F}$$E$tem um peso e os pesos das soluções (parciais) são apenas a soma dos pesos dos elementos. (Por exemplo, o peso de uma árvore de abrangência é a soma de seus pesos das arestas.) Nesse contexto, Helman et al. mostrou que o seguinte é equivalente:

1. Para cada função objetivo linear, tem uma base ideal.$(E,\mathcal{F})$

2. $(E,\mathcal{F})$ é uma incorporação matróide.

3. Para todas as funções objetivas lineares, as bases gananciosas de são exatamente suas bases ideais.$(E,\mathcal{F})$

Em outras palavras: para estruturas como essas (que basicamente incorporam o tipo de estrutura geralmente pensada ao trabalhar com a ganância), exatamente o conjunto de implantes matróides pode ser resolvido com avidez.

A definição de uma incorporação matróide não é tão difícil, portanto, é certamente viável provar que um determinado problema é ou não uma incorporação matróide. A entrada da Wikipedia fornece a definição com bastante clareza. (Compreender a prova de por que essas são as estruturas exatas solucionáveis ​​pela ganância - isso é outra questão inteiramente ...)

Se o seu problema pode ser formulado em termos de seleção de um sistema conjunto ponderada com uma função objetivo linear, e se você pode mostrar que é não uma incorporação matróides, então você mostrou que não pode ser resolvido com avidez, mesmo se você paraíso' Não foi possível encontrar um contra-exemplo. (Embora eu suspeito que encontrar um contra-exemplo seria um pouco mais fácil.)

Essa abordagem não é totalmente sem problemas, suponho. Como você diz, a idéia geral de ganância é bastante informal e pode ser possível ajustá-la de tal maneira que o formalismo de sistemas de conjuntos linearmente ponderados não se aplique.

Sim, existe esse trabalho. Allan Borodin, com os co-autores, desenvolveu uma teoria na qual formaliza a noção de ganância e obtém resultados que as relações de aproximação podem ser alcançadas com eles. Eles introduzem uma classe de algoritmos prioritários, que generaliza algoritmos gananciosos. Seu primeiro trabalho nesse tópico é o artigo " Algoritmos de prioridade (incremental) ".

PS O parágrafo anterior responde a uma pergunta diferente: É possível provar que, para um determinado problema, não existem algoritmos gananciosos com uma taxa de aproximação menor que ? O que diz respeito à questão, suponho que seja assumido que ótimo significa exato, de modo que a questão está relacionada a problemas em P (presumo que algoritmos gananciosos tenham complexidade polinomial, embora eu ache que isso não seja necessário), que são conhecidos por terem solução por outros métodos que não os gananciosos . E não sei a resposta para esta pergunta.$1+\epsilon$

Para ivotron: se você não quis dizer minha primeira interpretação, excluirei esta resposta.

Veja também: http://en.wikipedia.org/wiki/Greedoid