Algorithms for Assignment Problems
– "Needle in a Haystack" or "How to find an (almost) optimal resource allocation if there are more possible solutions than particles in the universe?" –
The research project deals with the design and analysis of algorithms for different combinatorial optimization problems that belong to the class of packing problems.
In packing problems the task is to choose a suitable subset of a given set of items and to find an assignment to bins such that a given objective function is optimized and constraints are fulfilled. Well-known problems are the knapsack problem or the generalized assignment problem.
Although it is often theoretically possible to enumerate all feasible solutions of a problem to determine an optimal solution, the computational effort for problem instances of realistic sizes is often too high. Thus, one is interested in approximation algorithm that yield after a short running time a specified quality guarantee compared to the optimal solution.
Within this research project new variants of these problems are investigated. If one considers additional minimum quantity constraints, the complexity of the problems increase and need new algorithmic approaches. Furthermore, variants are considered where constraints are relaxed such that instead of fixed capacity bounds costs depending on the workload are introduced and added as convex functions to the objective.
While the above mentioned problems deal with static assignment decisions, scheduling is concerned with the time aspect of how limited resources should be utilized by processes. A common problem in this field is the interval scheduling problem. Here, start and end times are given for every task, and the goal is to decide which tasks to accept such that the number of completed tasks is maximized. If all tasks are initially known, the problem can be modeled as a shortest path problem and solved using standard algorithms. The case where there is no information about future requests available has received little attention so far. Online optimization deals with the question how algorithms have to look like that can deal with the uncertainties.
The goal of all developed algorithm is to make use of limited resources most efficiently in order to contribute to decision making. This allows for cooperation with agricultural and forestry sciences, as well as business administration.