English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Minimizing Flow Time in the Wireless Gathering Problem

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2011). Minimizing Flow Time in the Wireless Gathering Problem. ACM Transactions on Algorithms, 7(3): 33, pp. 33:1-33:20. doi:10.1145/1978782.1978788.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-1254-9 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-057D-D
Genre: Journal Article

Files

show Files
hide Files
:
gathering-talg.pdf (Any fulltext), 279KB
 
File Permalink:
-
Name:
gathering-talg.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
© 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
License:
-

Locators

show

Creators

show
hide
 Creators:
Bonifaci, Vincenzo1, Author           
Korteweg, Peter2, Author
Marchetti-Spaccamela, Alberto2, Author
Stougie, Leen2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 618715
DOI: 10.1145/1978782.1978788
URI: http://doi.acm.org/10.1145/1978782.1978788
Other: Local-ID: C1256428004B93B8-AE0CC65BAC8BF1D3C1257979005FB068-Bonifaci:2011:b
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: ACM Transactions on Algorithms
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: 7 (3) Sequence Number: 33 Start / End Page: 33:1 - 33:20 Identifier: ISSN: 1549-6325