A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines

DOI10.1137/21M1469753OpenAlexW4307886765MaRDI QIDQ5048294

Pavel Veselý, Łukasz Jeż, Jiří Sgall, Marek Chrobak

Publication date: 15 November 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/21m1469753

zbMATH Keywords

online algorithmsbuffer managementpacket scheduling

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized competitive algorithms for online buffer management in the adaptive adversary model
• Online scheduling with partial job values: does timesharing or randomization help?
• A \(\phi\)-competitive algorithm for collecting items with increasing weights from a dynamic queue
• Collecting weighted items from a dynamic queue
• A universal randomized packet scheduling algorithm
• Online packet scheduling with bounded delay and lookahead
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online scheduling of packets with agreeable deadlines
• Competitive queue policies for differentiated services
• Analysis of queueing policies in QoS switches
• Buffer Overflow Management in QoS Switches
• Considering Suppressed Packets Improves Buffer Management in Quality of Service Switches
• Improved online algorithms for buffer management in QoS switches
• STACS 2004
• Algorithms – ESA 2004
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

This page was built for publication: A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines