File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642028823_36
 Scopus: eid_2s2.076249109836
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Online tree node assignment with resource augmentation
Title  Online tree node assignment with resource augmentation 

Authors  
Keywords  2trees Assignment problems Competitive algorithms Complete binary tree Hypercube 
Issue Date  2009 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, N.Y., 1315 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358367 How to Cite? 
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 at 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 leaftoroot 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/reassigments, 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 1competitive 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 2competitive algorithm with 3h/8+2 trees; (3) an amortized (4/3+α) competitive algorithm with (11/4+4/(3α)) trees, for any α where 0<α≤4/3. © 2009 Springer Berlin Heidelberg. 
Description  LNCS v. 5609 is Proceedings of the 15th Annual International Conference Session  TS11: Algorithms 
Persistent Identifier  http://hdl.handle.net/10722/93096 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, JWT  en_HK 
dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Ting, HF  en_HK 
dc.contributor.author  Zhang, Y  en_HK 
dc.date.accessioned  20100925T14:50:46Z   
dc.date.available  20100925T14:50:46Z   
dc.date.issued  2009  en_HK 
dc.identifier.citation  The 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, N.Y., 1315 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358367  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/93096   
dc.description  LNCS v. 5609 is Proceedings of the 15th Annual International Conference   
dc.description  Session  TS11: Algorithms   
dc.description.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 at 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 leaftoroot 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/reassigments, 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 1competitive 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 2competitive algorithm with 3h/8+2 trees; (3) an amortized (4/3+α) competitive algorithm with (11/4+4/(3α)) trees, for any α where 0<α≤4/3. © 2009 Springer Berlin Heidelberg.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  2trees   
dc.subject  Assignment problems   
dc.subject  Competitive algorithms   
dc.subject  Complete binary tree   
dc.subject  Hypercube   
dc.title  Online tree node assignment with resource augmentation  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.email  Ting, HF:hfting@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.identifier.authority  Ting, HF=rp00177  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783642028823_36  en_HK 
dc.identifier.scopus  eid_2s2.076249109836  en_HK 
dc.identifier.hkuros  162178  en_HK 
dc.identifier.hkuros  166449   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.076249109836&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  5609  en_HK 
dc.identifier.spage  358  en_HK 
dc.identifier.epage  367  en_HK 
dc.publisher.place  Germany  en_HK 
dc.description.other  The 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, N.Y., 1315 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358367   
dc.identifier.scopusauthorid  Chan, JWT=16021445200  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Ting, HF=7005654198  en_HK 
dc.identifier.scopusauthorid  Zhang, Y=7601329213  en_HK 