English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we study a scheduling problem arising from executing numericalsimulations on HPC architectures. With a constant number of parallel machines,the objective is to minimize the makespan under memory constraints for themachines. Those constraints come from a neighborhood graph G for the jobs.Motivated by a previous result on graphs G with bounded path-width, our focusis on the case when the neighborhood graph G has bounded tree-width. Our resultis a bi-criteria fully polynomial time approximation algorithm based on adynamic programming algorithm. It allows to find a solution within a factor of1 + epsilon of the optimal makespan, where the memory capacity of the machinesmay be exceeded by a factor at most 1 + epsilon. This result relies on the useof a nice tree decomposition of G and its traversal in a specific way which maybe useful on its own. The case of unrelated machines is also tractable withminor modifications.

A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graph with Bounded Tree-width