• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Parameterized Inapproximability of Target Set Selection and Generalizations

Thumbnail
Date
2014
Lien vers un document non conservé dans cette base
https://arxiv.org/abs/1403.3565v2
Indexation documentaire
Recherche opérationnelle
Subject
Target Set Selection problem
Code JEL
C.C4.C44
Réf version publiée
http://dx.doi.org/10.1007/978-3-319-08019-2_2
Titre de l'ouvrage
Language, Life, Limits.10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings
Auteur
Arnold Beckmann, Erzsébet Csuhaj-Varjú, Klaus Meer
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin Heidelberg
Année
2014
ISBN
978-3-319-08018-5
URL de l'ouvrage
10.1007/978-3-319-08019-2
URI
https://basepub.dauphine.fr/handle/123456789/15892
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Bazgan, Cristina
Chopin, Morgan
Nichterlein, André
Sikora, Florian
Type
Communication / Conférence
Nombre de pages du document
11-20
Résumé en anglais
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-08019-2_2/978-3-319-08019-2_2_IEq1_HTML.gif for each vertex v of the graph, find a minimum size vertex-subset to “activate” s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex v is activated during the propagation process if at least https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-08019-2_2/978-3-319-08019-2_2_IEq2_HTML.gif of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions f and ρ this problem cannot be approximated within a factor of ρ(k) in f(k) ·n O(1) time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimization versions of the problem for which we prove similar hardness results.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.