Citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778
Материал из DISCOPAL
«
Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях.
Сначала пытаемся выбрать среди определенных доступных узлов в сети, а затем, адаптивно, среди соседей этих узлов, когда они становятся доступными, чтобы максимизировать влияние на всю сеть.
Несмотря на недавние сильные результаты аппроксимации, очень мало известно о проблеме, когда узлы могут брать на себя различные затраты на активацию.
Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию
вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы.
В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют узлы с разнородной стоимостью активации.
Сначала мы показываем точный результат о приближаемости, который применяется даже для очень ограниченной версии проблемы.
Затем мы дополняем это примерно применимость с приближением постоянного множителя для общих субмодулярных функций, показывающая, что трудности, вызванные стохастической природой проблемы, могут быть преодолены.
Кроме того, мы показываем более сильные результаты аппроксимации для аддитивных функций влияния и случаев, когда узлы затраты на активацию составляют небольшую часть бюджета.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.