Recentemente, li algumas coisas sobre problemas de otimização incremental, mas não vejo qual é a diferença entre esses e os problemas de otimização on-line. Minha impressão é que posso definir todos os problemas on-line como uma contrapartida incremental (o inverso é claramente verdadeiro).
Aqui vão as definições (não muito formais). Em um problema incremental, é dada uma sequência de instâncias de um problema de otimização. A (i + 1) -ésima instância é uma "extensão" da i-ésima. A (i + 1) -ésima solução deve ser calculada sem o conhecimento das instâncias "futuras" e deve manter as decisões tomadas na i-ésima solução. O exemplo clássico está no problema da k-mediana: depois de abrir k instalações, queremos ter instalações k '> k, mas não queremos demolir as antigas.
Em um problema online, (a definição usual é essa), é dada uma sequência de "solicitações". Aqui, também é necessário responder a uma solicitação sem o conhecimento das solicitações futuras. Quer-se otimizar o custo / ganho de responder à sequência como um todo.
Acredito que, para qualquer problema online, eu possa definir um problema de otimização "offline" que se ajuste à definição incremental (e o que geralmente vejo é o contrário). Se as definições são equivalentes, qual é o sentido de usar um nome diferente para o mesmo conceito?
fonte
Respostas:
Isso é discutido na seção 2.2.3 da tese de Jeffrey Hartline: http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf
Os problemas on-line têm a ver com incerteza informacional: você não sabe quais contribuições virão amanhã, e a dificuldade geralmente é a teoria da informação, não a computacional. Por outro lado, não há incerteza em um problema de otimização incremental como Hartline o define: todos os parâmetros do problema são conhecidos desde o início. Sem restrições computacionais, os problemas sempre podem ser resolvidos de maneira ideal.
Talvez sua definição esteja errada, pois a sua parece um problema online. O problema da "otimização incremental" parece ser definido nesta tese de 2008 e difere da sua definição, pois não há incerteza.
fonte