охватывающее поддерево
Я собираюсь предположить, что вы имели в виду древовидность .Зафиксируйте корень u (или просто попробуйте все вершины для дополнительного множителя | V |).Для каждой дуги a пусть x a будет индикаторной переменной 0-1 для принадлежности к древовидности.Для каждой вершины v пусть y v будет одинаковым.Очевидная целочисленная программа:
максимизировать ∑ v прибыль ( v ) y v
∑ a стоимость ( a ) x a ≤ бюджет
∀ v ≠ и.10 S ⊆V, u∈ S , v ∉S. y v ≤ ∑ a ∈ S × (V ∖ S ) x a
∀ a . x a ∈ {0, 1}
∀ v . y v ∈ {0, 1}
К сожалению, разрыв в интегральности бесконечен.Имея ту же проблему с несколькими другими формулировками, я начинаю довольно сильно подозревать, что не существует алгоритма аппроксимации с «разумным» коэффициентом аппроксимации.Эта проблема в некотором роде сочетает механику покупки в натуральном выражении с проблемой максимального покрытия, заложенной в бюджет, что позволяет предельным издержкам дополнительного покрытия стать чрезвычайно дешевыми, что, как представляется, должно привести к тому типу порогового поведения, который исключает приближение,Одним из выходов может быть доведение до бикритериального приближения (т. Е. Придание алгоритму приближения большего бюджета).