A FPTAS for scheduling with memory constraints on graphs with bounded tree-width - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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

(1) , (2, 3) , (1)
1
2
3
Eric Angel
• Function : Author
• PersonId : 1102458
Sébastien Morais
• Function : Author
• PersonId : 952842
Damien Regnault
• Function : Author
• PersonId : 1102459

#### 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.

#### Domains

Computer Science [cs]

### Dates and versions

cea-03264475 , version 1 (18-06-2021)

### Identifiers

• HAL Id : cea-03264475 , version 1

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

59 View