A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width

DOI10.1007/978-3-031-12597-3_9MaRDI QIDQ6487362zbMATH OpenFDO

Authors Eric Angel, Sébastien Morais, Damien Regnault

Publication date 9 December 2022

Full work available at URL https://doi.org/10.1007/978-3-031-12597-3_9

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• FPT approximation algorithm for scheduling with memory constraints
• Approximation algorithms for time constrained scheduling
• Scheduling tree dags on parallel architectures

Cites work

• A 3/2-approximation algorithm for k_i-partitioning
• A comment on scheduling two parallel machines with capacity constraints
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An efficient PTAS for parallel machine scheduling with capacity constraints
• Approximating Scheduling Machines with Capacity Constraints
• Approximation algorithms for scheduling unrelated parallel machines
• Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• FPT approximation algorithm for scheduling with memory constraints
• Graph minors. I. Excluding a forest
• Treewidth. Computations and approximations
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(3)

• Scheduling series-parallel task graphs to minimize peak memory
• FPT approximation algorithm for scheduling with memory constraints
• Simultaneous Computational and Data Load Balancing in Distributed-Memory Setting

This page was built for publication: A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width

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