Achievable performance of blind policies in heavy traffic

N. Bansal; B. Kamphorst; B. Zwart

Achievable performance of blind policies in heavy traffic

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic

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-2	Engels
Artikelnummer	1512.07771
Aantal pagina's	22
Tijdschrift	arXiv
Status	Gepubliceerd - 24 dec 2015

Trefwoorden

math.PR
cs.DS

Toegang tot document

1512.07771v3

https://arxiv.org/abs/1512.07771

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

Citeer dit

@article{846996195d8d4d09ac1d06e7ca8685c8,

title = "Achievable performance of blind policies in heavy traffic",

abstract = "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.",

keywords = "math.PR, cs.DS",

author = "N. Bansal and B. Kamphorst and B. Zwart",

year = "2015",

month = dec,

day = "24",

language = "English",

journal = "arXiv",

publisher = "Cornell University Library",

}

TY - JOUR

T1 - Achievable performance of blind policies in heavy traffic

AU - Bansal, N.

AU - Kamphorst, B.

AU - Zwart, B.

PY - 2015/12/24

Y1 - 2015/12/24

N2 - 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.

AB - 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.

KW - math.PR

KW - cs.DS

M3 - Article

JO - arXiv

JF - arXiv

M1 - 1512.07771

ER -