Online tree node assignment with resource augmentation

Joseph Wun-Tat Chan (), Francis Y. L. Chin (), Hing-Fung Ting () and Yong Zhang ()
Additional contact information
Joseph Wun-Tat Chan: The University of Hong Kong
Francis Y. L. Chin: The University of Hong Kong
Hing-Fung Ting: The University of Hong Kong
Yong Zhang: The University of Hong Kong

Journal of Combinatorial Optimization, 2011, vol. 22, issue 3, No 5, 359-377

Abstract: Abstract Given a complete binary tree of height h, the online tree node assignment problem is to serve a sequence of assignment/release requests, where an assignment request, with an integer parameter 0≤i≤h, is served by assigning a (tree) node of level (or height) i and a release request is served by releasing a specified assigned node. The node assignments have to guarantee that no node is assigned to two assignment requests unreleased, and every leaf-to-root path of the tree contains at most one assigned node. With assigned node reassignments allowed, the target of the problem is to minimize the number of assignments/reassignments, i.e., the cost, to serve the whole sequence of requests. This online tree node assignment problem is fundamental to many applications, including OVSF code assignment in WCDMA networks, buddy memory allocation and hypercube subcube allocation. Most of the previous results focus on how to achieve good performance when the same amount of resource is given to both the online and the optimal offline algorithms, i.e., one tree. In this paper, we focus on resource augmentation, where the online algorithm is allowed to use more trees than the optimal offline algorithm. By using different approaches, we give (1) a 1-competitive online algorithm, which uses (h+1)/2 trees and is optimal because (h+1)/2 trees are required by any online algorithm to match the cost of the optimal offline algorithm with one tree; (2) a 2-competitive algorithm with 3h/8+2 trees; (3) an amortized 8/3-competitive algorithm with 11/4 trees; (4) a general amortized (4/3+α)-competitive algorithm with (11/4+4/(3α)) trees, for 0

Keywords: Online algorithms; Tree node assignment; Resource augmentation (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-010-9292-z 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:22:y:2011:i:3:d:10.1007_s10878-010-9292-z

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

DOI: 10.1007/s10878-010-9292-z

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 ().