Classi c Maximum Coverage (M C) - это проблема оптимизации NP-hard. Рассмотрим d элементов U = {e1, e2, ... ed} и c множеств T1, T2 ... T c. Каждый набор содержит несколько элементов в U. Задача состоит в том, чтобы найти не более b наборов, чтобы мощность объединения этих наборов была максимальной. Например, T1 = {e1, e3}, T2 = {e1, e2, e3} и T3 = {e3, e4}. Когда b = 2, оптимальное решение выбирает T2 и T3. Я рассматриваю вариант задачи classi c M C, который накладывает ограничение на размер набора. Рассмотрим 1 км C. Проблема все еще NP-трудная?
Моя гипотеза состоит в том, что кМ C все еще NP-труден, но я изо всех сил пытаюсь придумать полиномиальное сокращение от проверенной проблемы NP-hard, такой как M C , Для произвольного случая максимального покрытия, если бы я смог найти полиномиальную редукцию к моей задаче для всех k> 1, я могу заключить, что моя проблема также NP-трудна. Вот что я получил до сих пор:
- Когда k = d, задача тривиально эквивалентна classi c Maximum Coverage.
- Когда k = d-1, мы смотрим на данный экземпляр M C и видим, существует ли множество с размером d. Если есть, просто выберите это. В противном случае оно сводится к проблеме кМ C с k = d-1.
Когда k меньше d-1, я прибегаю к динамическому c программированию для завершения сокращения. Тем не менее, это приводит к неполиномиальному сокращению времени, что лишает цели сокращения NP-трудной задачи.
Если кто-нибудь может дать мне несколько советов о том, как мне следует решить эту проблему, или даже просто сделать обоснованное предположение о сложности проблемы кМ C (P или NP), я Я действительно ценю это.