Существуют ли какие-либо приблизительные алгоритмы в покрытии множеств, когда существует слишком много множеств, скажем, 2^n множеств?

Question

Существуют ли какие-либо приблизительные алгоритмы в покрытии множеств, когда существует слишком много множеств, скажем, 2^n множеств?

Я недавно работаю над проблемой, которая, на мой взгляд, является ответвлением проблемы установленного покрытия. Однако число наборов в моей задаче достигает 2^n. И приблизительные алогрифы, которые я нашел, кажутся эффективными только тогда, когда не слишком много наборов. Интересно, существует ли алгоритм, который подходит для 2 ^ n множеств?

Спасибо за ваш ответ!!!

2

algorithm set-cover

Источник

user879731 20 июн '12 в 08:02

1 ответ

Решение

Другие вопросы по тегам algorithm set-cover

user416926 20 июн '12 в 08:24 2012-06-20 08:24 · Accepted Answer · 2012-06-20 08:24

Нет, нет лучшего приближения, чем логарифмическое. см вики:

Результаты неприемлемости показывают, что жадный алгоритм, по сути, является наилучшим из возможных алгоритмов аппроксимации полиномиального времени для покрытия множества при предположениях вероятной сложности. Lund & Yannakakis (1994) показали, что покрытие множества не может быть аппроксимировано за полиномиальное время с точностью до 0,72 ln(n), если NP не имеет квазиполиномиальных временных алгоритмов.