Back to Search
Start Over
Randomized Two-Valued Bounded Delay Online Buffer Management
- Source :
- Operations Research Letters, Operations Research Letters, Elsevier, 2021, 49 (2), pp.246-249. ⟨10.1016/j.orl.2021.01.010⟩
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
Abstract
- In the bounded delay buffer management problem unit size packets arrive online to be sent over a network link. The objective is to maximize the total weight of packets sent before their deadline. In this paper we are interested in the two-valued variant of the problem, where every packet has either low (1) or high priority weight ( α > 1 ). We show that the optimal randomized competitive ratio against an oblivious adversary is 1 + ( α − 1 ) ∕ ( α 2 + α ) .
- Subjects :
- TheoryofComputation_MISCELLANEOUS
FOS: Computer and information sciences
Computer science
Bounded delay
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0211 other engineering and technologies
competitive ratio
02 engineering and technology
Management Science and Operations Research
01 natural sciences
Industrial and Manufacturing Engineering
Buffer (optical fiber)
010104 statistics & probability
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
0101 mathematics
Unit size
021103 operations research
oblivious adversary
Competitive analysis
business.industry
Network packet
Applied Mathematics
maximum throughput scheduling
Network link
Maximum throughput scheduling
business
Software
Computer network
buffer management
Subjects
Details
- ISSN :
- 01676377
- Database :
- OpenAIRE
- Journal :
- Operations Research Letters, Operations Research Letters, Elsevier, 2021, 49 (2), pp.246-249. ⟨10.1016/j.orl.2021.01.010⟩
- Accession number :
- edsair.doi.dedup.....68260abbaeb1ee40d7b0425fceb4ddd2
- Full Text :
- https://doi.org/10.48550/arxiv.2004.14715