Approximation algorithms for time-constrained scheduling on line networks

DOI10.1007/s00224-011-9351-6zbMath1253.68365OpenAlexW2063934256MaRDI QIDQ693767

Harald Räcke, Adi Rosén

Publication date: 10 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9351-6

zbMATH Keywords

approximation algorithmspacket schedulingline networkstime constraints

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Online time-constrained scheduling in linear and ring networks
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Approximations for the disjoint paths problem in high-diameter planar networks
• An overtraining-resistant stochastic modeling method for pattern recognition
• Time-constrained scheduling of weighted packets on trees and meshes
• Scheduling time-constrained communication in linear networks
• The network as a storage device: dynamic routing with bounded buffers
• Competitive weighted throughput analysis of greedy protocols on DAGs
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Probability Inequalities for Sums of Bounded Random Variables
• Algorithms – ESA 2005