Publikationen

In this paper we consider a generalized k-server problem with parallel requests where several servers can also be located on one point (which was initiated by an operations research problem). In section 4 the ''compound Harmonic algorithm'' for the generalized k-server problem is presented. Certain multi-step transition probabilities and absorbing probabilities are used by the compound Harmonic algorithm. For their computation one step of the generalized k-server problem is replaced by a number of steps of other (generalized) specific k-server problems. We show that this algorithm is competitive against an adaptive online adversary. In the case of unit distances the Harmonic algorithm and the compound Harmonic algorithm are identical.

Copositivity tests are presented based on new necessary and suffcient conditions requiring the solution of linear complementarity problems (LCP). Methodologies involving Lemke's method, an enumerative algorithm and a linear mixed-integer programming formulation are proposed to solve the required LCPs. A new necessary condition for (strict) copositivity based on solving a Linear Program (LP) is also discussed, which can be used as a preprocessing step. The algorithms with these three different variants are thoroughly applied to test matrices from the literature and to max-clique instances with matrices up to dimension 496 x 496. We compare our procedures with three other copositivity tests from the literature as well as with a general global optimization solver. The numerical results are very promising and equally good and in many cases better than the results reported elsewhere.