Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 457047

The design and analysis of a modified work function algorithm for solving the on-line k-server problem


Baumgartner, Alfonzo; Rudec, Tomislav; Manger, Robert
The design and analysis of a modified work function algorithm for solving the on-line k-server problem // Computing and informatics, 29 (2010), 4; 681-700 (međunarodna recenzija, članak, znanstveni)


CROSBI ID: 457047 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

Naslov
The design and analysis of a modified work function algorithm for solving the on-line k-server problem

Autori
Baumgartner, Alfonzo ; Rudec, Tomislav ; Manger, Robert

Izvornik
Computing and informatics (1335-9150) 29 (2010), 4; 681-700

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); moving windows; competitiveness; implementation; network flows; experiments; performance; computational complexity

Sažetak
In this paper we study a modified work function algorithm (WFA) for solving the on-line k-server problem. Our modification is based on a moving window, i.e. on an approximate work function that takes into account only a fixed number of most recent on-line requests. We give a precise specification of the modified WFA, investigate its competitiveness, and explain how it can be implemented efficiently by network flows. We also present experiments that measure the performance and computational complexity of the implemented algorithm. The results of the paper can be summarized as follows: the modified WFA is not competitive, but according to the experiments it still provides almost the same quality of serving as the original WFA while running much faster.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo



POVEZANOST RADA


Projekt / tema
036-0363078-3018 - Upravljanje mobilnim robotima i vozilima u nepoznatim i dinamičkim okruženjima (Ivan Petrović, )
037-0362980-2774 - Distribuirani algoritmi za pronalaženje optimalnih putova u grafovima (Robert Manger, )

Ustanove
Fakultet elektrotehnike i računarstva, Zagreb,
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb

Profili:

Avatar Url Tomislav Rudec (autor)

Avatar Url Robert Manger (autor)

Citiraj ovu publikaciju

Baumgartner, Alfonzo; Rudec, Tomislav; Manger, Robert
The design and analysis of a modified work function algorithm for solving the on-line k-server problem // Computing and informatics, 29 (2010), 4; 681-700 (međunarodna recenzija, članak, znanstveni)
Baumgartner, A., Rudec, T. & Manger, R. (2010) The design and analysis of a modified work function algorithm for solving the on-line k-server problem. Computing and informatics, 29 (4), 681-700.
@article{article, year = {2010}, pages = {681-700}, keywords = {on-line problems, on-line algorithms, k-server problem, work function algorithm (WFA), moving windows, competitiveness, implementation, network flows, experiments, performance, computational complexity}, journal = {Computing and informatics}, volume = {29}, number = {4}, issn = {1335-9150}, title = {The design and analysis of a modified work function algorithm for solving the on-line k-server problem}, keyword = {on-line problems, on-line algorithms, k-server problem, work function algorithm (WFA), moving windows, competitiveness, implementation, network flows, experiments, performance, computational complexity} }

Časopis indeksira:


  • Current Contents Connect (CCC)
  • Web of Science Core Collection (WoSCC)
    • Science Citation Index Expanded (SCI-EXP)
    • SCI-EXP, SSCI i/ili A&HCI
  • Scopus


Uključenost u ostale bibliografske baze podataka:


  • INSPEC
  • Zentrallblatt für Mathematik/Mathematical Abstracts