Верхняя граница коэффициента аппроксимации для жадного алгоритма для заданного покрытия (отдельные экземпляры)

Question

Умышленно у меня есть способ найти (и доказать) верхнюю границу коэффициента аппроксимации для жадного алгоритма, которую (границу) можно получить для отдельных случаев задачи покрытия множества. Для задач, которые у меня есть в моей библиотеке, эта граница отношения лучше, чем значения, которые мы можем получить, используя известные формулы для общего случая задачи.

Можно ли это как-то использовать? Или это бесполезный результат?

Answer 1

Другими словами, вы можете вычислить нижние границы для каждого экземпляра. Классический подход теории CS состоит в том, чтобы решить проблему дробной упаковки, которая двойственна релаксации LP покрытия набора: назначить каждому элементу, который должен быть покрыт неотрицательную стоимость, такую, что для каждого набора сумма затрат элементов в этом наборе равна самое большее стоимость набора. Цель состоит в том, чтобы максимизировать сумму по каждому элементу стоимости элемента.

Есть даже более сильные ослабления, которые обменивают вычислительные затраты на качество (например, вместо того, чтобы назначать затраты отдельным элементам, назначайте затраты подмножествам k элементов).