Home

Matthias Hellwig

  1. On the Value of Job Migration in Online Makespan Minimization.

    Fri, 11/04/2011 - 15:01 — SomNambul
    Authors: Matthias Hellwig, Susanne Albers
    Subjects: Data Structures and Algorithms
    Abstract

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

  2. Approximation Algorithms for Variable-Sized and Generalized Bin Covering.

    Mon, 09/19/2011 - 15:01 — SomNambul
    Authors: Alexander Souza, Matthias Hellwig
    Subjects: Data Structures and Algorithms
    Abstract

    In this paper, we consider the \alg{Generalized Bin Covering} 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$ (\alg{Bin Covering}) and $p_i = d_i$
    (\alg{Variable-Sized Bin Covering}) have been treated before.

Math-arch

Syndicate content