File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-02882-3_36
- Scopus: eid_2-s2.0-76249109836
- 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 | 2-trees 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., 13-15 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358-367 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 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. |
Description | LNCS v. 5609 is Proceedings of the 15th Annual International Conference Session - TS11: Algorithms |
Persistent Identifier | http://hdl.handle.net/10722/93096 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
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 | 2010-09-25T14:50:46Z | - |
dc.date.available | 2010-09-25T14:50:46Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | 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 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.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 | 2-trees | - |
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/978-3-642-02882-3_36 | en_HK |
dc.identifier.scopus | eid_2-s2.0-76249109836 | en_HK |
dc.identifier.hkuros | 162178 | en_HK |
dc.identifier.hkuros | 166449 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-76249109836&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., 13-15 July 2009. In Lecture Notes in Computer Science, 2009, v. 5609, p. 358-367 | - |
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 |
dc.identifier.issnl | 0302-9743 | - |