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 Library locked




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


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, Abstract, ©

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},
ADDRESS = {New York, NY},
ISBN = {1549-6325},
DOI = {10.1145/1978782.1978788},
}


Entry last modified by Anja Becker, 02/01/2012
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/02/2012 06:25:10 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Vincenzo Bonifaci
Vincenzo Bonifaci
Vincenzo Bonifaci
Edit Dates
01.02.2012 13:47:08
01.02.2012 13:46:48
01/02/2012 06:49:27 PM
01/02/2012 06:25:47 PM
01/02/2012 06:25:10 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
gathering-talg.pdf