Publications at the Institute of Mathematics

Results: 2081
Created on: Tue, 30 Apr 2024 23:07:53 +0200 in 0.0533 sec


Hildenbrandt, Regina;
The k-server problem with parallel requests and the compound work function algorithm. - In: Baltic journal of modern computing, ISSN 2255-8950, Bd. 8 (2020), 1, S. 1-20

In this paper the compound work function 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 1995 Koutsoupias and Papadimitriouhave proved that the well-known work function algorithm is competitive for the (usual) k-server problem. A proof, where a potential-like function argument is included, was given by Borodinand El-Yaniv in 1998. Unfortunately, certain techniques of these proofs cannot be applied to show that a natural generalization of the work function algorithm is competitive for the problem with parallel requests. Values of work functions, which are used by the compound work function algorithm are 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 work function algorithm is competitive with the same bound of the ratio as in the case of the usual problem.



https://doi.org/10.22364/bjmc.2020.8.1.01
Kriesell, Matthias;
Maximal ambiguously k-colorable graphs. - In: Journal of combinatorial theory, Bd. 140 (2020), S. 248-262

https://doi.org/10.1016/j.jctb.2019.05.007
Rocktäschel, Stefan;
A branch-and-bound algorithm for multiobjective mixed-integer convex optimization. - Wiesbaden : Springer Spektrum, 2020. - VIII, 70 Seiten. - (BestMasters) ISBN 978-3-658-29148-8

Sauerteig, Philipp; Worthmann, Karl
Towards multiobjective optimization and control of smart grids. - In: Optimal control, applications and methods, ISSN 1099-1514, Bd. 41 (2020), 1, S. 128-145

https://doi.org/10.1002/oca.2532
Preißer, Johanna E.; Schmidt, Jens M.
Computing vertex-disjoint paths in large graphs using MAOs. - In: Algorithmica, ISSN 1432-0541, Bd. 82 (2020), 1, S. 146-162

https://doi.org/10.1007/s00453-019-00608-2
Eichfelder, Gabriele; Niebling, Julia; Rocktäschel, Stefan
An algorithmic approach to multiobjective optimization with decision uncertainty. - In: Journal of global optimization, ISSN 1573-2916, Bd. 77 (2020), 1, S. 3-25

In real life applications, optimization problems with more than one objective function are often of interest. Next to handling multiple objective functions, another challenge is to deal with uncertainties concerning the realization of the decision variables. One approach to handle these uncertainties is to consider the objectives as set-valued functions. Hence, the image of one decision variable is a whole set, which includes all possible outcomes of this decision variable. We choose a robust approach and thus these sets have to be compared using the so-called upper-type less order relation. We propose a numerical method to calculate a covering of the set of optimal solutions of such an uncertain multiobjective optimization problem. We use a branch-and-bound approach and lower and upper bound sets for being able to compare the arising sets. The calculation of these lower and upper bound sets uses techniques known from global optimization, as convex underestimators, as well as techniques used in convex multiobjective optimization as outer approximation techniques. We also give first numerical results for this algorithm.



https://doi.org/10.1007/s10898-019-00815-9
Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Longer cycles in essentially 4-connected planar graphs. - In: Discussiones mathematicae, ISSN 2083-5892, Bd. 40 (2020), 1, S. 269-277

https://doi.org/10.7151/dmgt.2133
Braun, Philipp; Grüne, Lars; Kellett, Christopher M.; Weller, Steven R.; Worthmann, Karl
Towards price-based predictive control of a small-scale electricity network. - In: International journal of control, ISSN 1366-5820, Bd. 93 (2020), 1, S. 40-61

https://doi.org/10.1080/00207179.2017.1339329
Barros, Gil F.; Cavalar, Bruno P.; Mota, Guilherme Oliveira; Parczyk, Olaf
Anti-Ramsey threshold of cycles for sparse graphs. - In: Electronic notes in theoretical computer science, ISSN 1571-0661, Bd. 346 (2019), S. 89-98

https://doi.org/10.1016/j.entcs.2019.08.009
Mohr, Samuel;
Cycles through a set of specified vertices of a planar graph. - In: Acta mathematica Universitatis Comenianae, ISSN 0862-9544, Bd. 88 (2019), 3, S. 963-966