New algorithms for online rectangle filling with k-lookahead

Haitao Wang (), Amitabh Chaudhary () and Danny Z. Chen ()
Additional contact information
Haitao Wang: University of Notre Dame
Amitabh Chaudhary: University of Notre Dame
Danny Z. Chen: University of Notre Dame

Journal of Combinatorial Optimization, 2011, vol. 21, issue 1, No 5, 67-82

Abstract: Abstract We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic and randomized results for algorithms that are allowed a k-lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k−1)}-competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as k approaches +∞. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2. We also present a randomized online algorithm with a competitive ratio of 1+1/(k+1). Our final result is a closely matching lower bound (also proved in this paper) of $1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))$ on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results for randomized algorithms for this problem.

Keywords: Online algorithm; Competitive ratio; k-lookahead; Channel aware scheduling; Online rectangle filling (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9246-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:21:y:2011:i:1:d:10.1007_s10878-009-9246-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9246-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().