Minimizing flow time in the wireless gathering problem

Vincenzo Bonifaci*, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 Ω(m1/3) 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.

Original languageEnglish
Title of host publicationProceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
PublisherIBFI Schloss Dagstuhl
Pages109-120
Number of pages12
ISBN (Print)9783939897064
Publication statusPublished - 1 Jan 2008
Event25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 - Bordeaux, France
Duration: 21 Feb 200823 Feb 2008

Publication series

NameProceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

Conference

Conference25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
CountryFrance
CityBordeaux
Period21/02/0823/02/08

Keywords

  • Approximation algorithms
  • Data gathering
  • Distributed algorithms
  • Wireless networks

Fingerprint Dive into the research topics of 'Minimizing flow time in the wireless gathering problem'. Together they form a unique fingerprint.

Cite this