On Multi-threaded Metrical Task Systems
Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests ar...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein |
| Aporte de: |
| id |
paperaa:paper_15708667_v4_n3_p401_Feuerstein |
|---|---|
| record_format |
dspace |
| spelling |
paperaa:paper_15708667_v4_n3_p401_Feuerstein2023-06-12T16:50:45Z On Multi-threaded Metrical Task Systems J. Discrete Algorithms 2006;4(3):401-413 Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved. Fil:Strejilevich de Loma, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| language |
Inglés |
| orig_language_str_mv |
eng |
| topic |
Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems |
| spellingShingle |
Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. On Multi-threaded Metrical Task Systems |
| topic_facet |
Competitive analysis Multi-tasking systems On-line algorithms Paging Algorithms Computation theory Information analysis Online systems Problem solving Random processes Competitive analysis Multi-tasking systems Multi-threaded Metrical Task Systems On-line algorithms Multiprocessing systems |
| description |
Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved. |
| format |
Artículo Artículo publishedVersion |
| author |
Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. |
| author_facet |
Feuerstein, E. Seiden, S.S. Strejilevich de Loma, A. |
| author_sort |
Feuerstein, E. |
| title |
On Multi-threaded Metrical Task Systems |
| title_short |
On Multi-threaded Metrical Task Systems |
| title_full |
On Multi-threaded Metrical Task Systems |
| title_fullStr |
On Multi-threaded Metrical Task Systems |
| title_full_unstemmed |
On Multi-threaded Metrical Task Systems |
| title_sort |
on multi-threaded metrical task systems |
| publishDate |
2006 |
| url |
http://hdl.handle.net/20.500.12110/paper_15708667_v4_n3_p401_Feuerstein |
| work_keys_str_mv |
AT feuersteine onmultithreadedmetricaltasksystems AT seidenss onmultithreadedmetricaltasksystems AT strejilevichdelomaa onmultithreadedmetricaltasksystems |
| _version_ |
1769810299812052992 |