Просмотр исходного текста страницы Citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778

{{checked|}}
{{citeseerlink|citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778|<html>
Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях.

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

Несмотря на недавние сильные результаты аппроксимации, очень мало известно о проблеме, когда узлы могут брать на себя различные затраты на активацию.  

Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию
вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы.

В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют  узлы с разнородной стоимостью активации.  

Сначала мы показываем точный результат о приближаемости, который применяется даже для очень ограниченной версии проблемы.  

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

Кроме того, мы показываем более сильные результаты аппроксимации для аддитивных функций влияния и случаев, когда узлы затраты на активацию составляют небольшую часть бюджета.
</html>}}
{{enddiv}}