Algoritmos Online

Algoritmos online devem tomar decisões irrevogáveis à medida que a entrada chega, sem conhecimento de requisições futuras; sua qualidade é medida por análise competitiva contra um algoritmo ótimo que vê toda a entrada antecipadamente.

Definition

Um algoritmo online recebe sua entrada como uma sequência de requisições e deve responder a cada uma imediatamente e irrevogavelmente sem ver requisições futuras; sua razão competitiva é a razão no pior caso de seu custo para o custo de um algoritmo offline ótimo que conhece toda a sequência de requisições.

Scope

Este tópico abrange algoritmos que processam a entrada sequencialmente e se comprometem com decisões antes que a entrada posterior seja conhecida, e a estrutura de razão competitiva usada para avaliá-los contra um adversário offline ótimo. Inclui problemas clássicos — paginação e cache, atualização de lista, o problema do aluguel de esqui, o problema do k-servidor, e escalonamento online e empacotamento de caixas — e o papel da randomização na melhoria das razões competitivas contra adversários mais fracos.

Core questions

• Como os algoritmos online são avaliados quando o futuro é desconhecido?
• O que a razão competitiva mede, e o que é o adversário offline?
• Como problemas clássicos como paginação e aluguel de esqui ilustram as compensações online?
• Como a randomização pode melhorar a competitividade contra um adversário alheio?
• Quais limites inferiores restringem o quão competitivo qualquer algoritmo online pode ser?

Key concepts

• online versus offline
• razão competitiva
• adversário offline
• paginação e cache
• atualização de lista
• problema do aluguel de esqui
• problema do k-servidor
• competitividade randomizada

Key theories

Análise competitiva

A análise competitiva julga um algoritmo online pela razão de pior caso entre seu custo e o de um algoritmo offline ótimo, fornecendo uma garantia que se mantém contra qualquer sequência de entrada, em vez de depender de suposições sobre a entrada.

Randomização contra adversários alheios

Algoritmos online randomizados podem alcançar razões competitivas estritamente melhores do que qualquer algoritmo determinístico contra um adversário alheio, porque o adversário deve fixar a entrada sem conhecer as escolhas aleatórias do algoritmo.

Clinical relevance

Algoritmos online modelam decisões que os sistemas tomam em tempo real sem conhecimento futuro: substituição de cache e página em sistemas operacionais e CPUs, auto-organização de estruturas de dados, alocação dinâmica de recursos e balanceamento de carga, e decisões de alugar ou comprar em computação em nuvem. A análise competitiva oferece garantias de pior caso para tais sistemas reativos.

History

A análise competitiva foi introduzida por Sleator e Tarjan em 1985 através de seu estudo das regras de atualização de lista e paginação, reformulando a avaliação de algoritmos online em torno da comparação com uma solução offline ótima. A estrutura se expandiu através do problema do k-servidor e algoritmos online randomizados na década de 1990, pesquisados na monografia de Borodin e El-Yaniv de 1998.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

O que é a razão competitiva?

É a razão no pior caso do custo de um algoritmo online para o custo de um algoritmo ótimo que vê toda a entrada antecipadamente. Um algoritmo 2-competitivo nunca custa mais do que o dobro do melhor custo offline possível em qualquer sequência de entrada.

Por que a randomização ajuda os algoritmos online?

Contra um adversário alheio que fixa a entrada sem ver as escolhas aleatórias do algoritmo, a randomização impede que o adversário adapte um pior caso ao comportamento do algoritmo, permitindo razões competitivas estritamente melhores do que qualquer algoritmo determinístico pode alcançar.