Quais são os problemas com a melhor taxa de aproximação alcançada pelo algoritmo que retorna solução aleatoriamente uniforme?

12

Quais são os problemas com a taxa de aproximação mais conhecida alcançada por um algoritmo retornando uma solução uniformemente aleatória?

Conheço um exemplo para o problema de fluxo de permutação : no artigo " Limites apertados para agendamento de lojas de fluxo de permutação " Viswanath Nagarajan e Maxim Sviridenko provaram que a sequência aleatória de tarefas tem garantia 2 F|perm|Cmax (m-número de máquinas en- número de postos de trabalho), que é o melhor conhecido actualmente.2min{m,n}mn

Oleksandr Bondarenko
fonte
10
Max3SAT? ------
Tsuyoshi Ito
AFAIK, Max3SAT se encaixa aqui.
Oleksandr Bondarenko

Respostas:

18

Para problemas de satisfação de restrições, a propriedade de não ter melhor algoritmo de aproximação que a atribuição aleatória é conhecida como resistência de aproximação .

PNP

Boaz Barak
fonte
isso é legal. Eu não tinha ideia de que esse conceito existia.
Suresh Venkat
12

De acordo com Guraswami et al, FOCS '08 , a conjectura exclusiva de jogos implicaria que não há algoritmo de aproximação para o conjunto máximo de arestas acíclicas de um dígrafo significativamente melhor do que aquele que permuta aleatoriamente os vértices e inclui uma aresta quando passa de um anterior a um vértice posterior na permutação (com razão de aproximação 1/2).

David Eppstein
fonte