Online tree node assignment with resource augmentation

Joseph W T CHAN, Francis Y.L. Chin, Hing Fung Ting, Yong Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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<α≤4/3.

Original languageEnglish
Pages (from-to)359-377
Number of pages19
JournalJournal of Combinatorial Optimization
Volume22
Issue number3
DOIs
Publication statusPublished - Oct 2011

Scopus Subject Areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Online algorithms
  • Resource augmentation
  • Tree node assignment

Fingerprint

Dive into the research topics of 'Online tree node assignment with resource augmentation'. Together they form a unique fingerprint.

Cite this