AWAndreas Wiese

Andreas Wiese

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Andreas Wiese has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio

    by Elisabeth Günther, Olaf Maurer, Nicole Megow, Andreas Wiese

    We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of competitive-ratio approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possi- ble competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal com- petitive ratio to a question that a computer can answer. We believe that our concept can also be applied to many other problems and yields a new perspective on online algorithms in general.

  • Partitioned EDF scheduling on a few types of unrelated multiprocessors

    by Andreas Wiese, Vincenzo Bonifaci, Sanjoy Baruah


  • Open Access

    Scheduling Unrelated Machines of Few Different Types

    by Vincenzo Bonifaci, Andreas Wiese

    A very well-known machine model in scheduling allows the machines to be unrelated, modelling jobs that might have different characteristics on each machine. Due to its generality, many optimization problems of this form are very difficult to tackle and typically APX-hard. However, in many applications the number of different types of machines, such as processor cores, GPUs, etc. is very limited. In this paper, we address this point and study the assignment of jobs to unrelated machines in the case that each machine belongs to one of a fixed number of types and the machines of each type are identical. We present polynomial time approximation schemes (PTASs) for minimizing the makespan for multidimensional jobs with a fixed number of dimensions and for minimizing the L_p-norm. In particular, our results subsume and generalize the existing PTASs for a constant number of unrelated machines and for an arbitrary number of identical machines for these problems. We employ a number of techniques which go beyond the previously known results, including a new counting argument and a method for making the concept of sparse extreme point solutions usable for a convex program.