Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/31648
Title: Approximation algorithms for disjoint st-paths with minimum activation cost
Authors: Alqahtani, Hasna Mohsen
Erlebach, Thomas
First Published: 2013
Presented at: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013.
Publisher: Springer Verlag (Germany)
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7878 LNCS, pp. 1-12
Abstract: In network activation problems we are given a directed or undirected graph G = (V,E) with a family {f (x, x) : (u,v) ∈ E} of monotone non-decreasing activation functions from D to {0,1}, where D is a constant-size domain. The goal is to find activation values x for all v ∈ V of minimum total cost Σ x such that the activated set of edges satisfies some connectivity requirements. Network activation problems generalize several problems studied in the network literature such as power optimization problems. We devise an approximation algorithm for the fundamental problem of finding the Minimum Activation Cost Pair of Node-Disjoint st-Paths (MA2NDP). The algorithm achieves approximation ratio 1.5 for both directed and undirected graphs. We show that a ρ-approximation algorithm for MA2NDP with fixed activation values for s and t yields a ρ-approximation algorithm for the Minimum Activation Cost Pair of Edge-Disjoint st-Paths (MA2EDP) problem. We also study the MA2NDP and MA2EDP problems for the special case |D| = 2.
Series/Report no.: Lecture Notes in Computer Science;7878
DOI Link: 10.1007/978-3-642-38233-8_1
ISSN: 0302-9743
ISBN: 978-3-642-38232-1
eISSN: 1611-3349
Links: http://link.springer.com/chapter/10.1007%2F978-3-642-38233-8_1
http://hdl.handle.net/2381/31648
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-38233-8_1
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
CIAC2013FinalAuthorVersion.pdfPost-review (final submitted)327.1 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.