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 √ (m-número de máquinas en- número de postos de trabalho), que é o melhor conhecido actualmente.
ds.algorithms
reference-request
approximation-algorithms
Oleksandr Bondarenko
fonte
fonte
Respostas:
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 .
fonte
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).
fonte
Em seu artigo " Aproximação ideal para o problema de bem-estar submodular no modelo Oracle Value ", Jan Vondrak afirma:
fonte