Source author record

Matthias Hellwig

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

3works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Online Makespan Minimization with Parallel Schedules

In online makespan minimization a sequence of jobs $σ= J_1,..., J_n$ has to be scheduled on $m$ identical parallel machines so as to minimize the maximum completion time of any job. We investigate the problem with an essentially new model of resource augmentation. Here, an online algorithm is allowed to build several schedules in parallel while processing $σ$ . At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. We develop a $(4/3+\eps)$-competitive algorithm, for any $0<\eps\leq 1$, that uses a number of $1/\eps^{O(\log (1/\eps))}$ schedules. We also give a $(1+\eps)$-competitive algorithm, for any $0<\eps\leq 1$, that builds a polynomial number of $(m/\eps)^{O(\log (1/\eps) / \eps)}$ schedules. This value depends on $m$ but is independent of the input $σ$ . The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4/3 must construct $Ω(m)$ schedules. Our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of a job sequence $σ$ to within a factor of $1+\eps$ and (2) guess the job processing times and their frequencies in $σ$ . In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant. The competitive ratios achieved using parallel schedules are considerably smaller than those in the standard problem without resource augmentation.

preprint2012arXiv

Approximation Algorithms for Variable-Sized and Generalized Bin Covering

We consider the Generalized Bin Covering (GBC) problem: We are given $m$ bin types, where each bin of type $i$ has profit $p_i$ and demand $d_i$ . Furthermore, there are $n$ items, where item $j$ has size $s_j$ . A bin of type $i$ is covered if the set of items assigned to it has total size at least the demand $d_i$ . In that case, the profit of $p_i$ is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases $p_i = d_i = 1$ (Bin Covering) and $p_i = d_i$ (Variable-Sized Bin Covering (VSBC)) have been treated before. We study two models of bin supply: In the unit supply model, we have exactly one bin of each type, i.\,e., we have individual bins. By contrast, in the infinite supply model, we have arbitrarily many bins of each type. Clearly, the unit supply model is a generalization of the infinite supply model. To the best of our knowledge the unit supply model has not been studied yet. Our results for the unit supply model hold not only asymptotically, but for all instances. This contrasts most of the previous work on \prob{Bin Covering}. We prove that there is a combinatorial 5-approximation algorithm for GBC with unit supply, which has running time $\bigO{nm\sqrt{m+n}}$. Furthermore, for VSBC we show that the natural and fast Next Fit Decreasing ($\NFD$) algorithm is a 9/4-approximation in the unit supply model. The bound is tight for the algorithm and close to being best-possible. We show that there is an AFPTAS for VSBC in the \emph{infinite} supply model.

preprint2012arXiv

On the Value of Job Migration in Online Makespan Minimization

Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of $n$ jobs has to be scheduled non-preemptively on $m$ machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range $[1.88,1.9201]$ . Currently no randomized online algorithm with a smaller competitiveness is known, for general $m$ . In this paper we explore the power of job migration, i.e.\ an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is $α_m$ -competitive, for any $m\geq 2$ , where $α_m$ is the solution of a certain equation. For $m=2$ , $α_2 = 4/3$ and $\lim_{m\rightarrow \infty} α_m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2)) \approx 1.4659$ . Here $W_{-1}$ is the lower branch of the Lambert $W$ function. For $m\geq 11$ , the algorithm uses at most $7m$ migration operations. For smaller $m$ , $8m$ to $10m$ operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses $o(n)$ job migrations can achieve a competitive ratio smaller than $α_m$ . We finally trade performance for migrations. We give a family of algorithms that is $c$ -competitive, for any $5/3\leq c \leq 2$ . For $c= 5/3$ , the strategy uses at most $4m$ job migrations. For $c=1.75$ , at most $2.5m$ migrations are used.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.