Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Bonifaci, Vincenzo Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen dblp dblp dblp dblp Not MPG Author(s): Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen
 BibTeX cite key*: Bonifaci:2011:b

 Title
 Title*: Minimizing Flow Time in the Wireless Gathering Problem Attachment(s): gathering-talg.pdf (278.32 KB)

 Journal
 Journal Title*: ACM Transactions on Algorithms Journal's URL: http://talg.acm.org/ Download URL for the article: http://doi.acm.org/10.1145/1978782.1978788 Language: English

 Publisher
 Publisher's Name: ACM Publisher's URL: http://www.acm.org Publisher's Address: New York, NY ISSN: 1549-6325

 Vol, No, pp, Date
 Volume*: 7 Number: 3 Publishing Date: 2011 Pages*: 33:1-33:20 Number of VG Pages: Page Start: 33:1 Page End: 33:20 Sequence Number: 33 DOI: 10.1145/1978782.1978788

 Note: (LaTeX) Abstract: We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow time and minimization of the average flow time of the packets. For both problems we prove that, unless P=NP, no polynomial-time algorithm can approximate the optimal solution within a factor less than $\Omega(m^{1-\epsilon})$ for any $0<\epsilon<1$, where $m$ is the number of packets. We then assess the performance of two natural algorithms by proving that their cost remains within the optimal cost of the respective problem if we allow the algorithms to transmit data at a speed 5 times higher than that of the optimal solutions to which we compare them. URL for the Abstract: Categories, Keywords: Wireless networks, Data gathering, Approximation algorithm, Local algorithm HyperLinks / References / URLs: Copyright Message: © ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM TRANSACTIONS ON ALGORITHMS, {7, 3, July 2011} http://doi.acm.org/10.1145/1978782.1978788 Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Bonifaci:2011:b,
AUTHOR = {Bonifaci, Vincenzo and Korteweg, Peter and Marchetti-Spaccamela, Alberto and Stougie, Leen},
TITLE = {Minimizing Flow Time in the Wireless Gathering Problem},
JOURNAL = {ACM Transactions on Algorithms},
PUBLISHER = {ACM},
YEAR = {2011},
NUMBER = {3},
VOLUME = {7},
PAGES = {33:1--33:20},