File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online tree node assignment with resource augmentation

TitleOnline tree node assignment with resource augmentation
Authors
KeywordsAssignment problems
Competitive algorithms
Complete binary tree
Hypercube
Integer parameters
Issue Date2011
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal of Combinatorial Optimization, 2011, v. 22 n. 3, p. 359-377 How to Cite?
AbstractGiven 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. © 2010 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152467
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
Funding AgencyGrant Number
HK RGCHKU-7113/07
HKU-7171/08E
Funding Information:

F.Y.L. Chin was supported by HK RGC grant HKU-7113/07E.

References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorZhang, Yen_US
dc.date.accessioned2012-06-26T06:39:27Z-
dc.date.available2012-06-26T06:39:27Z-
dc.date.issued2011en_US
dc.identifier.citationJournal of Combinatorial Optimization, 2011, v. 22 n. 3, p. 359-377en_US
dc.identifier.issn1382-6905en_US
dc.identifier.urihttp://hdl.handle.net/10722/152467-
dc.description.abstractGiven 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. © 2010 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_US
dc.relation.ispartofJournal of Combinatorial Optimizationen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAssignment problemsen_US
dc.subjectCompetitive algorithmsen_US
dc.subjectComplete binary treeen_US
dc.subjectHypercube-
dc.subjectInteger parameters-
dc.titleOnline tree node assignment with resource augmentationen_US
dc.typeArticleen_US
dc.identifier.emailChan, JWT: wtchan@cs.hku.hken_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hk-
dc.identifier.emailZhang, Y: yongzh@hkucc.hku.hk-
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10878-010-9292-zen_US
dc.identifier.scopuseid_2-s2.0-80053109338en_US
dc.identifier.hkuros208032-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80053109338&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume22en_US
dc.identifier.issue3en_US
dc.identifier.spage359en_US
dc.identifier.epage377en_US
dc.identifier.isiWOS:000294536500005-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridZhang, Y=35114314500en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridChan, JWT=16021445200en_US
dc.identifier.citeulike6839215-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats