Citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778

Ссылки сюда (1) →

«Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778»^{скачать}

« Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях. Сначала пытаемся выбрать среди определенных доступных узлов в сети, а затем, адаптивно, среди соседей этих узлов, когда они становятся доступными, чтобы максимизировать влияние на всю сеть. Несмотря на недавние сильные результаты аппроксимации, очень мало известно о проблеме, когда узлы могут брать на себя различные затраты на активацию. Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы. В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют узлы с разнородной стоимостью активации. Сначала мы показываем точный результат о приближаемости, который применяется даже для очень ограниченной версии проблемы. Затем мы дополняем это примерно применимость с приближением постоянного множителя для общих субмодулярных функций, показывающая, что трудности, вызванные стохастической природой проблемы, могут быть преодолены. Кроме того, мы показываем более сильные результаты аппроксимации для аддитивных функций влияния и случаев, когда узлы затраты на активацию составляют небольшую часть бюджета. …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.