Better approximation algorithms for technology diffusion

Jochen Könemann, Sina Sadeghian, Laura Sanità

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)


Motivated by cascade effects arising in network technology upgrade processes in the Internet, Goldberg and Liu [SODA, 2013] recently introduced the following natural technology diffusion problem. Given a graph G = (V,E), and thresholds θ(v), for all v ∈ V. A vertex u activates if it is adjacent to a connected component of active nodes of size at least θ(v). The goal is to find a seed set whose initial activation would trigger a cascade activating the entire graph. Goldberg and Liu presented an algorithm for this problem that returns a seed set of size O(rl log(n)) times that of an optimum seed set, where r is the diameter of the given graph, and l is the number of distinct thresholds used in the instance. We improve upon this result by presenting an O( min {r,l} log(n))-approximation algorithm. Our algorithm is simple and combinatorial, in contrast with the previous approach that is based on randomized rounding applied to the solution of a linear program.

Originele taal-2Engels
TitelAlgorithms, ESA 2013 - 21st Annual European Symposium, Proceedings
Aantal pagina's10
StatusGepubliceerd - 2013
Extern gepubliceerdJa
Evenement21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, Frankrijk
Duur: 2 sep 20134 sep 2013

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8125 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres21st Annual European Symposium on Algorithms, ESA 2013
StadSophia Antipolis


Duik in de onderzoeksthema's van 'Better approximation algorithms for technology diffusion'. Samen vormen ze een unieke vingerafdruk.

Citeer dit