Approximation algorithms for time-constrained scheduling on line networks

DOI10.1007/S00224-011-9351-6MaRDI QIDQ693767zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A Constant Approximation Algorithm for Scheduling Packets on Line Networks
• Time-constrained scheduling of weighted packets on trees and meshes
• Scheduling time-constrained communication in linear networks
• Online time-constrained scheduling in linear and ring networks
• Online scheduling of packets with agreeable deadlines

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 2079411 (Why is no real title available?)
• Algorithms – ESA 2005
• An overtraining-resistant stochastic modeling method for pattern recognition
• Approximations for the disjoint paths problem in high-diameter planar networks
• Online time-constrained scheduling in linear and ring networks
• Probability Inequalities for Sums of Bounded Random Variables
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Scheduling time-constrained communication in linear networks
• The network as a storage device: dynamic routing with bounded buffers
• Time-constrained scheduling of weighted packets on trees and meshes

Cited in

(6)

• A Constant Approximation Algorithm for Scheduling Packets on Line Networks
• Online time-constrained scheduling in linear and ring networks
• Time optimal linear schedules for algorithms with uniform dependencies
• Scheduling time-constrained communication in linear networks
• Link scheduling in polynomial time
• Time-constrained scheduling of weighted packets on trees and meshes

This page was built for publication: Approximation algorithms for time-constrained scheduling on line networks

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