### Abstract

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.

Original language | English |
---|---|

Title of host publication | Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings |

Pages | 637-646 |

Number of pages | 10 |

DOIs | |

Publication status | Published - 2013 |

Externally published | Yes |

Event | 21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 2013 |

### Publication series

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

Volume | 8125 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 21st Annual European Symposium on Algorithms, ESA 2013 |
---|---|

Country | France |

City | Sophia Antipolis |

Period | 2/09/13 → 4/09/13 |

### Keywords

- Approximation Algorithms
- Combinatorial Optimization
- Technology Diffusion

## Fingerprint Dive into the research topics of 'Better approximation algorithms for technology diffusion'. Together they form a unique fingerprint.

## Cite this

*Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings*(pp. 637-646). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8125 LNCS). https://doi.org/10.1007/978-3-642-40450-4_54