Improved approximation algorithms for maximum lifetime problems in wireless networks

DOI10.1016/J.TCS.2011.08.001zbMATH Open1252.68039OpenAlexW2181264742MaRDI QIDQ714776FDOQ714776

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

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

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)

Cites Work

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

Cited In (4)

• Exact and performance-guaranteed multicast algorithms for lifetime optimization in WANETs
• Approximation bounds on the number of mixedcast rounds in wireless ad-hoc networks
• 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)