On the Complexity of Approximation and Online Scheduling Problems with Applications to Optical Networks

DOI10.1007/978-3-662-53174-7_3zbMath1417.90084OpenAlexW2489258616MaRDI QIDQ2827800

Shmuel Zaks

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_3

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Minimizing total busy time in parallel scheduling with application to optical networks
• On linear k-arboricity
• Optimal on-line colorings for minimizing the number of ADMs in optical networks
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Some APX-completeness results for cubic graphs
• Traffic partition in WDM/SONET rings to minimize SONET ADMs
• The regenerator location problem
• On Minimizing the Number of ADMs in a General Topology Optical Network
• Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
• Approximation and Online Algorithms