A Better Algorithm for Uniform Metrical Task Systems with Few States

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Wolfgang Bein Articles by Lawrence Larmore Articles by John Noga

8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)

Las Vegas, Nevada, USA

December 07-December 09

ISBN: 0-7695-2509-1

	ASCII Text	x
	Wolfgang Bein, Lawrence Larmore, John Noga, "A Better Algorithm for Uniform Metrical Task Systems with Few States," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 94-99, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005.

	BibTex	x
	@article{ 10.1109/ISPAN.2005.5, author = {Wolfgang Bein and Lawrence Larmore and John Noga}, title = {A Better Algorithm for Uniform Metrical Task Systems with Few States}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {2005}, issn = {1087-4089}, pages = {94-99}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.5}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - A Better Algorithm for Uniform Metrical Task Systems with Few States SN - 1087-4089 SP94 EP99 A1 - Wolfgang Bein, A1 - Lawrence Larmore, A1 - John Noga, PY - 2005 KW - online algorithms KW - randomized algorithms KW - task systems VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Wolfgang Bein, UNLV

Lawrence Larmore, UNLV

John Noga, Cal State, Northridge

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.5

We give a randomized algorithm( the "Wedge Algorithm") of competitiveness \frac{3}{2}H_k - \frac{1}{{2K}} for any metrical task system on a uniform space of K points, for any k \ge 2, where H_k = \sum\nolimits_{i = 1}^k \frac{1}{i}, the k^th This algorithm has better competitiveness than Irani-Seidan algorithm if k ia smaller than 10^8. The algorithm is better by a factor of 2 if k \le 47.

Index Terms:

online algorithms, randomized algorithms, task systems

Citation:

Wolfgang Bein, Lawrence Larmore, John Noga, "A Better Algorithm for Uniform Metrical Task Systems with Few States," ispan, pp.94-99, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.