Minimizing flow time in the wireless gathering problem

Vincenzo Bonifaci; Peter Korteweg; Alberto Marchetti-Spaccamela; Leen Stougie

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 proceeding › Conference contribution › Academic › peer-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 Ω(m^1/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 language	English
Title of host publication	Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
Publisher	IBFI Schloss Dagstuhl
Pages	109-120
Number of pages	12
ISBN (Print)	9783939897064
Publication status	Published - 1 Jan 2008
Event	25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 - Bordeaux, France Duration: 21 Feb 2008 → 23 Feb 2008

Publication series

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

Conference

Conference	25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
Country/Territory	France
City	Bordeaux
Period	21/02/08 → 23/02/08

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Approximation algorithms
Data gathering
Distributed algorithms
Wireless networks

Persistent URL (handle)

Persistent link

Cite this

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2008). Minimizing flow time in the wireless gathering problem. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 (pp. 109-120). (Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008). IBFI Schloss Dagstuhl.

Bonifaci, Vincenzo ; Korteweg, Peter ; Marchetti-Spaccamela, Alberto et al. / Minimizing flow time in the wireless gathering problem. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008. IBFI Schloss Dagstuhl, 2008. pp. 109-120 (Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008).

@inproceedings{f37ab7fb9cd14f4eb0e006c46cd1066d,

title = "Minimizing flow time in the wireless gathering problem",

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.",

keywords = "Approximation algorithms, Data gathering, Distributed algorithms, Wireless networks",

author = "Vincenzo Bonifaci and Peter Korteweg and Alberto Marchetti-Spaccamela and Leen Stougie",

year = "2008",

month = jan,

day = "1",

language = "English",

isbn = "9783939897064",

series = "Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008",

publisher = "IBFI Schloss Dagstuhl",

pages = "109--120",

booktitle = "Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008",

note = "25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 ; Conference date: 21-02-2008 Through 23-02-2008",

}

Bonifaci, V, Korteweg, P, Marchetti-Spaccamela, A & Stougie, L 2008, Minimizing flow time in the wireless gathering problem. in Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008, IBFI Schloss Dagstuhl, pp. 109-120, 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008, Bordeaux, France, 21/02/08.

Minimizing flow time in the wireless gathering problem. / Bonifaci, Vincenzo; Korteweg, Peter; Marchetti-Spaccamela, Alberto et al.
Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008. IBFI Schloss Dagstuhl, 2008. p. 109-120 (Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Minimizing flow time in the wireless gathering problem

AU - Bonifaci, Vincenzo

AU - Korteweg, Peter

AU - Marchetti-Spaccamela, Alberto

AU - Stougie, Leen

PY - 2008/1/1

Y1 - 2008/1/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Data gathering

KW - Distributed algorithms

KW - Wireless networks

UR - https://www.scopus.com/pages/publications/45749124408

UR - https://www.scopus.com/pages/publications/45749124408#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:45749124408

SN - 9783939897064

T3 - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

SP - 109

EP - 120

BT - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

PB - IBFI Schloss Dagstuhl

T2 - 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

Y2 - 21 February 2008 through 23 February 2008

ER -

Minimizing flow time in the wireless gathering problem

Abstract

Publication series

Conference

UN SDGs

Keywords

Persistent URL (handle)

Other files and links

Fingerprint

Cite this