TY - GEN

T1 - Better approximation algorithms for technology diffusion

AU - Könemann, Jochen

AU - Sadeghian, Sina

AU - Sanità, Laura

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Approximation Algorithms

KW - Combinatorial Optimization

KW - Technology Diffusion

UR - http://www.scopus.com/inward/record.url?scp=84884337974&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40450-4_54

DO - 10.1007/978-3-642-40450-4_54

M3 - Conference contribution

AN - SCOPUS:84884337974

SN - 9783642404498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 637

EP - 646

BT - Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings

T2 - 21st Annual European Symposium on Algorithms, ESA 2013

Y2 - 2 September 2013 through 4 September 2013

ER -