Improved approximation algorithms for maximum lifetime problems in wireless networks

DOI10.1016/J.TCS.2011.08.001MaRDI QIDQ714776zbMATHOpenAlexFDO

Authors Zeev Nutov, Michael Segal

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.08.001

zbMATH Keywords

optimization methodssensor networksad-hoc networkslow power algorithmslow power protocolsminimal energy control

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Recommendations

• Approximation bounds on the number of mixedcast rounds in wireless ad-hoc networks
• Network lifetime and power assignment in ad hoc wireless networks
• Maximum Lifetime Broadcasting in Wireless Networks
• Bounded-hops power assignment in ad hoc wireless networks
• Algorithmic Applications in Management

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Additive guarantees for degree-bounded directed network design
• Algorithms for energy-efficient multicasting in static ad hoc wireless networks
• Approximating Directed Weighted-Degree Constrained Networks
• Approximating minimum bounded degree spanning trees to within one of optimal
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks.
• Exact and approximate balanced data gathering in energy-constrained sensor networks
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast algorithm for multicast and data gathering in wireless networks
• Handbook of Approximation Algorithms and Metaheuristics
• Matroid Intersection
• Maximum Lifetime Broadcasting in Wireless Networks
• Maximum lifetime data sensing and extraction in energy constrained networked sensor systems
• Survivable network design with degree or order constraints

Cited in

(4)

• Approximation bounds on the number of mixedcast rounds in wireless ad-hoc networks
• Exact and performance-guaranteed multicast algorithms for lifetime optimization in WANETs
• Maximum Lifetime Broadcasting in Wireless Networks
• Lifetime maximization routing with network coding in wireless multihop networks

This page was built for publication: Improved approximation algorithms for maximum lifetime problems in wireless networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714776)