Какие проблемы с наилучшим коэффициентом аппроксимации достигаются алгоритмом, возвращающим равномерно случайное решение?

Какие проблемы с наилучшим известным коэффициентом аппроксимации достигаются алгоритмом, возвращающим равномерно случайное решение?

Я знаю один такой пример для задачи магазина перестановок : в статье « Тесные границы для планирования потока перестановок » Вишванат Нагараджан и Максим Свириденко доказали, что случайная последовательность заданий имеет гарантию 2 $F|perm|C_{max}$ (m-количество машин иn-количествозаданий), которое является наиболее известным в настоящее время.$2\sqrt{min\{m,n\}}$$m$$n$

Для задач удовлетворения ограничений свойство отсутствия лучшего алгоритма аппроксимации, чем случайное назначение, называется сопротивлением аппроксимации .

$P\neq NP$

Согласно Guraswami et al., FOCS '08 , гипотеза об уникальных играх подразумевает, что не существует алгоритма аппроксимации для набора максимальных ациклических ребер орграфа, значительно лучшего, чем тот, который случайным образом переставляет вершины и включает ребро, когда оно выходит из раньше к более поздней вершине в перестановке (с отношением приближения 1/2).

В своей статье « Оптимальное приближение для субмодулярной проблемы благосостояния в модели стоимостного Oracle » Ян Вондрак утверждает:

$n$$(1 − \frac{1}{e})$