Implementation of approximation algorithms for the max-min resource sharing problem, Experimental Algorithms

Abstract. We implement the algorithm for the max-min resource shar-ing problem described in [7], using a new line search technique for de-termining a suitable step length. Our line search technique uses a mod-ified potential function that is less costly to evaluate, thus heuristically simplifying the computation. Observations concerning the quality of the dual solution and oscillating behavior of the algorithm are made. First numerical observations are briefly discussed. In particular we study a certain class of linear programs, namely the computational bottleneck of an algorithm from [8] for solving strip packing with an approach from [10, 13]. For these, we obtain practical running times. Our implementa-tion is able to solve instances for small accuracy parameters for which the methods proposed in theory are out of practical interest. More pre-cisely, the technique from [8] improves the known runtime bound of O(M6 ln2(Mn/(at)) + M5n/t + ln(Mn/(at))) to the more favourable bound O(M(−3(−2 + lnM) +M(−2 + lnM))), where n denotes the number of items, M the number of distinct item widths, a the width of the narrowest item and t is a desired additive tolerance. Keywords