A -Competitive Algorithm for Scheduling Packets with Deadlines

DOI10.1137/21M1469753MaRDI QIDQ5048294zbMATH OpenOpenAlexFDO

Authors 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

buffer managementonline algorithmspacket scheduling

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Recommendations

• A -competitive algorithm for scheduling packets with deadlines
• Online scheduling of packets with agreeable deadlines
• A -competitive algorithm for collecting items with increasing weights from a dynamic queue
• Online packet scheduling with bounded delay and lookahead
• An optimal online algorithm for packet scheduling with agreeable deadlines

Cites work

• A -competitive algorithm for collecting items with increasing weights from a dynamic queue
• A universal randomized packet scheduling algorithm
• Algorithms – ESA 2004
• An optimal online algorithm for packet scheduling with agreeable deadlines
• Analysis of queueing policies in QoS switches
• Better online buffer management
• Buffer Overflow Management in QoS Switches
• Collecting weighted items from a dynamic queue
• Competitive queue policies for differentiated services
• Considering suppressed packets improves buffer management in quality of service switches
• scientific article; zbMATH DE number 2079410 (Why is no real title available?)
• Improved online algorithms for buffer management in QoS switches
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online packet scheduling with bounded delay and lookahead
• Online scheduling of packets with agreeable deadlines
• Online scheduling with partial job values: does timesharing or randomization help?
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Randomized competitive algorithms for online buffer management in the adaptive adversary model
• Randomized primal-dual analysis of RANKING for online bipartite matching
• STACS 2004

Cited in

(2)

• A Constant Approximation Algorithm for Scheduling Packets on Line Networks
• Breaking the barrier of 2 for the competitiveness of longest queue drop

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048294)