Vector scheduling with rejection on two machines.

In this paper, we study the problem of vector scheduling with rejection on two identical parallel machines, where the objective is to minimize the sum of maximum load over all dimensions and machines and the total penalty cost. We present a 3-approximation algorithm and a 2.54-approximation algorithm based randomized rounding for the general case. When the number of dimensions is fixed, we design a fully polynomial time approximation scheme based on dynamic programming. Finally, we design an online algorithm with competitive ratio 1.62d, where d is the number of dimensions. [ABSTRACT FROM AUTHOR]