Napredna pretraga

Pregled bibliografske jedinice broj: 540487

A fast work function algorithm for solving the k-server problem


Rudec, Tomislav; Baumgartner, Alfonzo; Manger, Robert
A fast work function algorithm for solving the k-server problem // Central European Journal of Operations Research, 21 (2013), 1; 187-205 doi:10.1007/s10100-011-0222-7 (međunarodna recenzija, članak, znanstveni)


Naslov
A fast work function algorithm for solving the k-server problem

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

Izvornik
Central European Journal of Operations Research (1435-246X) 21 (2013), 1; 187-205

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; implementation. network flows

Sažetak
This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper addresses some practical aspects of the WFA, such as its efficient implementation and its true quality of serving. First, an implementation of the WFA is proposed, which is based on network flows, and which reduces each step of the WFA to only one minimal-cost maximal flow problem instance. Next, it is explained how the proposed implementation can further be simplified if the involved metric space is finite. Also, it is described how actual computing of optimal flows can be speeded up by taking into account special properties of the involved networks. Some experiments based on the proposed implementation and improvements are presented, where actual serving costs of the WFA have been measured on very large problem instances and compared with costs of other algorithms. Finally, suitability of the WFA for solving real-life problems is discussed.

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
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb

Časopis indeksira:


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


Uključenost u ostale bibliografske baze podataka:


  • MathSciNet
  • Zentrallblatt für Mathematik/Mathematical Abstracts


Citati