Publications

In many real-world optimization problems, a solution cannot be realized in practice exactly as computed, e.g., it may be impossible to produce a board of exactly 3.546˜mm width. Whenever computed solutions are not realized exactly but in a perturbed way, we speak of decision uncertainty. We study decision uncertainty in multiobjective optimization problems and we propose the concept decision robust efficiency for evaluating the robustness of a solution in this case. Therefore, we address decision uncertainty within the framework of set-valued maps. First, we prove that convexity and continuity are preserved by the resulting set-valued mappings. Second, we obtain specific results for particular classes of objective functions that are relevant for solving the set-valued problem. We furthermore prove that decision robust efficient solutions can be found by solving a deterministic problem in case of linear objective functions. We also investigate the relationship of the proposed concept to other concepts in the literature.

In this paper the (randomized) compound Harmonic algorithm for solving the generalized k-server problem is proposed. This problem is an online k-server problem with parallel requests where several servers can also be located on one point. In 2000 Bartal and Grove have proved that the well-known Harmonic algorithm is competitive for the (usual) k-server problem. Unfortunately, certain techniques of this proof cannot be used to show that a natural generalization of the Harmonic algorithm is competitive for the problem with parallel requests. The probabilities, which are used by the compound Harmonic algorithm are, finally, derived from a surrogate problem, where at most one server must be moved in servicing the request in each step. We can show that the compound Harmonic algorithm is competitive with the bound of the ratio as which has been proved by Bartal and Grove in the case of the usual problem.