Load Balancing: The Long Road from Theory to Practice

被引：0

作者：

Berndt, Sebastian ^{[1
]}

Deppert, Max A. ^{[2
]}

Jansen, Klaus ^{[2
]}

Rohwedder, Lars ^{[3
]}

机构：

[1] Univ Lubeck, Lubeck, Germany

[2] Univ Kiel, Kiel, Germany

[3] Ecole Polytech Fed Lausanne, Lausanne, Switzerland

来源：

2022 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX | 2022年

关键词：

BIN-PACKING; MAKESPAN;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a p1 qapproximation solution for every epsilon > 0, but the running time grows exponentially in 1/epsilon. For a long time, these schemes seemed like a purely theoretical concept. Even solving instances for moderate values of " seemed completely illusional. In an effort to bridge theory and practice, we refine recent ILP techniques to develop the fastest known approximation scheme for this problem. An implementation of this algorithm reaches values of " lower than 2/11 approximate to 18:2% within a reasonable timespan. This is the approximation guarantee of MULTIFIT, which, to the best of our knowledge, has the best proven guarantee of any non-scheme algorithm.

引用

页码：104 / 116

页数：13

共 30 条

[1]

Alon N, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P493

[2]

Ayaz Dzul fikar M., 2019, Leibniz International Proceedings in Informatics (LIPIcs), V148

[3] INTEGER-MAKING THEOREMS [J].