Аппроксимационный алгоритм для ограниченного максимального охватывающего поддерева для направленного графа

Question

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

Answer 1

остовным поддерево

Я буду считать, что вы имели в виду в arborescence. Исправьте корень u (или просто попробуйте все вершины для дополнительного коэффициента | V |). Для каждой дуги a, x _a be a 0-1 индикаторная переменная для членства в arborescence. Для каждой вершины v, y _v быть таким же. Очевидным целое программа

увеличить ∑ _v прибыли (v) у _v
∑ стоимость () х ≤ бюджет
& forall; v ≠ u. &для всех; S & subseteq; V, U ∈ S, против ∉ С. у _против ≤ ∑ _{∈ S × (V & setminus; S)}х
& forall; a. x _a ∈ {0, 1}
& forall; v. у _v ∈ {0, 1}

К сожалению, разрыв целочисленность бесконечно. Имея ту же проблему с несколькими другими формулировками, я начинаю подозревать довольно сильно, что нет алгоритма аппроксимации с приемлемым отношением ”. Эта проблема объединяет механизм покупки навалом с бюджетной проблемой максимального охвата, позволяя предельные издержки дополнительного покрытия стать чрезвычайно дешевыми, что, похоже, должно привести к типу порогового поведения, которое исключает аппроксимацию ,Одним из путей может быть согласие на бикритрическое приближение (т. Е. Дать алгоритму аппроксимации больший бюджет).