日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
 
 
ダウンロード電子メール
 タグ情報を表示リリース履歴を表示詳細要約
  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):, pp. 33:1-33:20. doi:10.1145/1978782.1978788.

Item is

 

表示: 全項目 非表示: 全項目

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0010-1254-9 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0024-057D-D
資料種別: 学術論文

ファイル

表示: ファイル
非表示: ファイル
:
gathering-talg.pdf (全文テキスト（全般）), 279KB
 
ファイルのパーマリンク:
-
ファイル名:
gathering-talg.pdf
説明:
-
OA-Status:
閲覧制限:
非公開
MIMEタイプ / チェックサム:
application/pdf
技術的なメタデータ:
著作権日付:
-
著作権情報:
© 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
CCライセンス:
-

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Bonifaci, Vincenzo1, 著者           
Korteweg, Peter2, 著者
Marchetti-Spaccamela, Alberto2, 著者
Stougie, Leen2, 著者
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

内容説明

表示:
非表示:
キーワード: -
 要旨: 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.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 20112011
 出版の状態: 出版
 ページ: -
 出版情報: -
 目次: -
 査読: 査読あり
 識別子（DOI, ISBNなど）: eDoc: 618715
DOI: 10.1145/1978782.1978788
URI: http://doi.acm.org/10.1145/1978782.1978788
その他: Local-ID: C1256428004B93B8-AE0CC65BAC8BF1D3C1257979005FB068-Bonifaci:2011:b
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: ACM Transactions on Algorithms
種別: 学術雑誌
 著者・編者:
所属:
出版社, 出版地: New York, NY : ACM
ページ: - 巻号: 7 (3) 通巻号: 33 開始・終了ページ: 33:1 - 33:20 識別子（ISBN, ISSN, DOIなど）: ISSN: 1549-6325