Approximation algorithms for time-constrained scheduling on line networks

DOI10.1007/S00224-011-9351-6zbMATH Open1253.68365OpenAlexW2063934256MaRDI QIDQ693767FDOQ693767

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

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

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

• An overtraining-resistant stochastic modeling method for pattern recognition
• Probability Inequalities for Sums of Bounded Random Variables
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• The network as a storage device: dynamic routing with bounded buffers
• Algorithms – ESA 2005
• Approximations for the disjoint paths problem in high-diameter planar 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
• Competitive weighted throughput analysis of greedy protocols on dags
• Title not available (Why is that?)

Cited In (6)

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

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)