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

Question

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

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

Answer 1

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

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