Randomized competitive algorithms for online buffer management in the adaptive adversary model

DOI10.1016/J.TCS.2011.05.015zbMath1222.68048OpenAlexW2134822363MaRDI QIDQ719250

Marek Chrobak, Marcin Bienkowski, Łukasz Jeż

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.015

zbMATH Keywords

competitive analysisbuffer managementonline schedulingpacket schedulingadaptive adversary

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items (5)

A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines ⋮ An optimal lower bound for buffer management in multi-queue switches ⋮ Comparison-based buffer management in QoS switches ⋮ A universal randomized packet scheduling algorithm ⋮ An optimal algorithm for 2-bounded delay buffer management with lookahead

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of randomization in on-line algorithms
• Online scheduling with partial job values: does timesharing or randomization help?
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Analysis of queueing policies in QoS switches
• Buffer Overflow Management in QoS Switches
• Algorithms – ESA 2004
• Approximation and Online Algorithms

This page was built for publication: Randomized competitive algorithms for online buffer management in the adaptive adversary model