File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online tree node assignment with resource augmentation

TitleOnline tree node assignment with resource augmentation
Authors
Keywords2-trees
Assignment problems
Competitive algorithms
Complete binary tree
Hypercube
Issue Date2009
PublisherSpringer 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., 13-15 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358-367 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 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 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/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 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 (4/3+α)- competitive algorithm with (11/4+4/(3α)) trees, for any α where 0<α≤4/3. © 2009 Springer Berlin Heidelberg.
DescriptionLNCS v. 5609 is Proceedings of the 15th Annual International Conference
Session - TS11: Algorithms
Persistent Identifierhttp://hdl.handle.net/10722/93096
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-09-25T14:50:46Z-
dc.date.available2010-09-25T14:50:46Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, N.Y., 13-15 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358-367en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93096-
dc.descriptionLNCS v. 5609 is Proceedings of the 15th Annual International Conference-
dc.descriptionSession - TS11: Algorithms-
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 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 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/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 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 (4/3+α)- competitive algorithm with (11/4+4/(3α)) trees, for any α where 0<α≤4/3. © 2009 Springer Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subject2-trees-
dc.subjectAssignment problems-
dc.subjectCompetitive algorithms-
dc.subjectComplete binary tree-
dc.subjectHypercube-
dc.titleOnline tree node assignment with resource augmentationen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-02882-3_36en_HK
dc.identifier.scopuseid_2-s2.0-76249109836en_HK
dc.identifier.hkuros162178en_HK
dc.identifier.hkuros166449-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-76249109836&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5609en_HK
dc.identifier.spage358en_HK
dc.identifier.epage367en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 15th International Computing and Combinatorics Conference (COCOON 2009), Niagara Falls, N.Y., 13-15 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358-367-
dc.identifier.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats