Achievable performance of blind policies in heavy traffic

N. Bansal, B. Kamphorst, B. Zwart

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

63 Downloads (Pure)

Samenvatting

For a GI/GI/1 queue, we show that the average sojourn time under the (blind) Randomized Multilevel Feedback algorithm is no worse than that under the Shortest Remaining Processing Time algorithm times a logarithmic function of the system load. Moreover, it is verified that this bound is tight in heavy traffic, up to a constant multiplicative factor. We obtain this result by combining techniques from two disparate areas: competitive analysis and applied probability.
Originele taal-2Engels
Artikelnummer1512.07771
Aantal pagina's22
TijdschriftarXiv
StatusGepubliceerd - 24 dec 2015

Trefwoorden

  • math.PR
  • cs.DS

Vingerafdruk Duik in de onderzoeksthema's van 'Achievable performance of blind policies in heavy traffic'. Samen vormen ze een unieke vingerafdruk.

Citeer dit