Citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778|<html> </html>}} {{enddiv}}») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
{{citeseerlink|citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778|<html> | {{citeseerlink|citeseer/Approximability of Adaptive Seeding under Knapsack Constraints (2015) 10.1.1.697.7778|<html> | ||
| + | Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях. | ||
| + | Сначала пытаемся выбрать среди определенных доступных узлов в сети, а затем, адаптивно, среди соседей этих узлов, когда они становятся доступными, чтобы максимизировать влияние на всю сеть. | ||
| + | Несмотря на недавние сильные результаты аппроксимации, очень мало известно о проблеме, когда узлы могут брать на себя различные затраты на активацию. | ||
| + | |||
| + | Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию | ||
| + | вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы. | ||
| + | |||
| + | В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют узлы с разнородной стоимостью активации. | ||
| + | |||
| + | Сначала мы показываем точный результат о приближаемости, который применяется даже для очень ограниченной версии проблемы. | ||
| + | |||
| + | Затем мы дополняем это примерно применимость с приближением постоянного множителя для общих субмодулярных функций, показывающая, что трудности, вызванные стохастической природой проблемы, могут быть преодолены. | ||
| + | |||
| + | Кроме того, мы показываем более сильные результаты аппроксимации для аддитивных функций влияния и случаев, когда узлы затраты на активацию составляют небольшую часть бюджета. | ||
</html>}} | </html>}} | ||
{{enddiv}} | {{enddiv}} | ||
Текущая версия на 09:27, 23 ноября 2021
«
Adapting Seeding («Адаптивный Посев™») — ключевая алгоритмическая задача выяснения максимизации влияния в социальных сетях.
Сначала пытаемся выбрать среди определенных доступных узлов в сети, а затем, адаптивно, среди соседей этих узлов, когда они становятся доступными, чтобы максимизировать влияние на всю сеть.
Несмотря на недавние сильные результаты аппроксимации, очень мало известно о проблеме, когда узлы могут брать на себя различные затраты на активацию.
Удивительно, но разработка адаптивного алгоритма, которые могут соответствующим образом мотивировать пользователей разнородными затратами на активацию
вводит фундаментальные проблемы, которых нет в упрощенной версии проблемы.
В этой статье мы изучаем аппроксимируемость алгоритмов адаптивного посева, которые стимулируют узлы с разнородной стоимостью активации.
Сначала мы показываем точный результат о приближаемости, который применяется даже для очень ограниченной версии проблемы.
Затем мы дополняем это примерно применимость с приближением постоянного множителя для общих субмодулярных функций, показывающая, что трудности, вызванные стохастической природой проблемы, могут быть преодолены.
Кроме того, мы показываем более сильные результаты аппроксимации для аддитивных функций влияния и случаев, когда узлы затраты на активацию составляют небольшую часть бюджета.
…»