Improved approximation algorithms for maximum lifetime problems in wireless networks

DOI10.1016/j.tcs.2011.08.001zbMath1252.68039OpenAlexW2181264742MaRDI QIDQ714776

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

sensor networksoptimization methodsad-hoc networkslow power algorithmslow power protocolsminimal energy control

Mathematics Subject Classification ID

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

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Fast algorithm for multicast and data gathering in wireless networks
• Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks.
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Maximum lifetime data sensing and extraction in energy constrained networked sensor systems
• Exact and approximate balanced data gathering in energy-constrained sensor networks
• Matroid Intersection
• Handbook of Approximation Algorithms and Metaheuristics
• Maximum Lifetime Broadcasting in Wireless Networks
• Approximating Directed Weighted-Degree Constrained Networks
• 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
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Algorithms for energy-efficient multicasting in static ad hoc wireless networks