Применение метода назначения цены для минимизации стоимости

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

Значение cs может рассматриваться как «доля» элемента s в стоимости. Утверждение (11.9) показывает, что модель долевого участия cs очень естественна, так как сумма долей равна стоимости покрытия множества C,  возвращаемой алгоритмом.

Ключом к доказательству того, что алгоритм является H(d*)-аппроксимирующим, было некоторое приближенное свойство «справедливости» долей стоимости: (11.10) показывает, что оплата за элементы множества Sk превосходит стоимость покрытия их множеством Sk не более чем в H(|Sk|) раз.

В этом разделе мы воспользуемся методом назначения цены на другом примере — на примере задачи о вершинном покрытии. И снова вес wi вершины i будет рассматриваться как стоимость использования i в покрытии.

Каждое ребро e будет рассматриваться как отдельный «агент», желающий «заплатить» что-то покрывающему его узлу.

Алгоритм будет не только находить вершинное покрытие S, но и определять цены pe ≥ 0 для каждого ребра e Ѯ E, так что если каждое ребро e Ѯ E платит цену pe, в сумме это приблизительно покроет стоимость S. Цены   pe являются аналогами cs из алгоритма о покрытии множества.