Scheduling with interjob communication on parallel processors

DOI10.1007/S10878-018-0325-3zbMath1414.90155OpenAlexW4232946180MaRDI QIDQ1631686

Friedhelm Meyer auf der Heide, Jürgen König, Alexander Mäcker, Sören Riechers

Publication date: 6 December 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0325-3

zbMATH Keywords

schedulingapproximation algorithmsbin packingNP hardnessshared resource

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• Parallelism versus memory allocation in pipelined router forwarding engines
• Bin packing can be solved within 1+epsilon in linear time
• Forests, frames, and games: Algorithms for matroid sums and applications
• Scheduling shared continuous resources on many-cores
• Partition into triangles on bounded degree graphs
• Approximation schemes for packing splittable items with cardinality constraints
• Improved results for a memory allocation problem
• Degree Bounded Forest Covering
• Approximation Schemes for Packing Splittable Items with Cardinality Constraints

This page was built for publication: Scheduling with interjob communication on parallel processors