Minimizing flow time in the wireless gathering problem

DOI10.1145/1978782.1978788zbMATH Open1295.68040arXiv0802.2836OpenAlexW2148438817MaRDI QIDQ3189016FDOQ3189016

Authors: Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, L. Stougie 

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than $$ when $m$ packets have to be transmitted, unless $P=NP$. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.

Full work available at URL: https://arxiv.org/abs/0802.2836

Recommendations

• Minimizing flow time in the wireless gathering problem
• An approximation algorithm for the wireless gathering problem
• An Approximation Algorithm for the Wireless Gathering Problem
• The Distributed Wireless Gathering Problem
• The distributed wireless gathering problem
• A MAX-Flow/MIN-Cut algorithm for a class of wireless networks
• Optimal gathering protocols on paths under interference constraints
• The minimum scheduling time for convergecast in wireless sensor networks

zbMATH Keywords

approximation algorithmswireless networkslocal algorithmsdata gathering

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cited In (9)

• An approximation algorithm for the wireless gathering problem
• Minimizing flow time in the wireless gathering problem
• Maximum Induced Matchings in Grids
• Induced matchings in strongly biconvex graphs and some algebraic applications
• The distributed wireless gathering problem
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matching algorithms via vertex ordering characterizations
• The Distributed Wireless Gathering Problem
• An Approximation Algorithm for the Wireless Gathering Problem

This page was built for publication: Minimizing flow time in the wireless gathering problem

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