Achievable Performance of Blind Policies in Heavy Traffic

Nikhil Bansal · Bart Kamphorst · Bert P. Zwart

14 citations0/0 files storedMathematics of Operations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Queuing Theory Analysis Optimization and Search Problems Age of Information Optimization

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 14 citations exist upstream.

References

2003Applied Probability and Queues 1968Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline 2001Largest Weighted Delay First Scheduling: Large Deviations and Optimality 2007The Foreground–Background queue: A survey 2007Tails in scheduling 2004Diffusion approximation for a processor sharing queue in heavy traffic 2012Is Tail-Optimal Scheduling Possible?1990On extremal service disciplines in single-stage queueing systems

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.