Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A FPTAS for scheduling with memory constraints on graphs with bounded tree-width

Abstract : In this paper we study the scheduling problem under memory constraints, noted P k|G, mem|C$_{max}$, that arise from executing numerical simulations on HPC architectures. We assume that the tree-width of the graph G is bounded by a constant, and we present a fully polynomial time approximation scheme (FPTAS) based on a dynamic programming algorithm. It allows to find a solution within a factor of $1 + \epsilon$ of the optimal makespan, where the capacity of the machines may be exceeded by a factor at most $1 + \epsilon$. This result extends somehow a previous fixed-parameter tractable algorithm with respect to the path-width of the graph G, and rely on the use of a nice tree decomposition of G and its traversal in a specific way which may be useful on its own. The case of unrelated machines, i.e. Rk|G, mem|C$_{max}$, is also tractable with minor modifications.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-cea.archives-ouvertes.fr/cea-03264475
Contributor : Sébastien Morais <>
Submitted on : Friday, June 18, 2021 - 11:33:52 AM
Last modification on : Tuesday, July 13, 2021 - 11:28:25 AM

File

FPTAS_SMC_Bounded_TW.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : cea-03264475, version 1

Citation

Eric Angel, Sébastien Morais, Damien Regnault. A FPTAS for scheduling with memory constraints on graphs with bounded tree-width. 2021. ⟨cea-03264475⟩

Share

Metrics

Record views

41

Files downloads

7