Online competitive algorithms for maximizing weighted throughput of unit jobs

DOI10.1016/j.jda.2005.03.005zbMath1132.68317OpenAlexW2168012204MaRDI QIDQ2458928

Wojciech Jawor, Marek Chrobak, Stanley P. Y. Fung, Francis Y. L. Chin, Jiří Sgall, Tomas Tichý

Publication date: 5 November 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.03.005

zbMATH Keywords

randomized algorithmbuffer managementonline unit-job scheduling problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Network design and communication in computer systems (68M10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items

A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines ⋮ Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints ⋮ Randomized two-valued bounded delay online buffer management ⋮ Competitive buffer management with packet dependencies ⋮ A comprehensive study of an online packet scheduling algorithm ⋮ Bounded delay packet scheduling in a bounded buffer ⋮ Online packet scheduling with bounded delay and lookahead ⋮ Collecting weighted items from a dynamic queue ⋮ Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs ⋮ Online buffer management for transmitting packets with processing cycles ⋮ An optimal lower bound for buffer management in multi-queue switches ⋮ Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints ⋮ Comparison-based buffer management in QoS switches ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Buffer management for colored packets with deadlines ⋮ A universal randomized packet scheduling algorithm ⋮ Randomized competitive algorithms for online buffer management in the adaptive adversary model ⋮ Improved Randomized Online Scheduling of Unit Length Intervals and Jobs ⋮ Randomized Algorithms for Buffer Management with 2-Bounded Delay ⋮ An optimal algorithm for 2-bounded delay buffer management with lookahead ⋮ Online algorithms for the maximum \(k\)-interval coverage problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preemptive scheduling in overloaded systems.
• Online scheduling with partial job values: does timesharing or randomization help?
• Competitive queue policies for differentiated services
• Improved Competitive Algorithms for Online Scheduling with Partial Job Values
• Nearly optimal FIFO buffer management for DiffServ
• Buffer overflow management in QoS switches
• STACS 2004
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Algorithms - ESA 2003

This page was built for publication: Online competitive algorithms for maximizing weighted throughput of unit jobs