In this proposal we consider graph parameters for directed graphs. We are interested in directed versions of clique-width, NLC-width, and rankwidth as well as several approaches for a directed version of tree-width. We want to obtain results in the field of graph theory as well as in algorithmic of special graphs.
funded by the German Research Foundation (DFG)
Algorithms for Controlling Stack-up Systems
This proposal considers the design and analysis of efficient algorithms for discrete optimization problems occurring in the field of controlling stack-up systems in delivery industry. We are given bins which are arriving unordered on a conveyor belt and which have to be rearranged with respect to customer orders in order to stack them up using the available resources from the conveyor belts onto pallets. The rearrangement must be restricted to the existing buffer options and methods of repositioning. Efficient control for such stack-up systems in delivery industry can reduce the costs for the execution of orders. The development of such control systems requires a detailed theoretical analysis of the underlying combinatorial problems. To this end the focus in this proposal is on modeling of stack-up systems and the solution of the resulting algorithmic problems.
cooperation with Prof. Jochen Rethmann (Hochschule Niederrhein)
Algorithms for Knapsack Problems
The knapsack problem (KP) is one of the most famous NP-hard tasks in combinatorial optimization. The input consists of a set $A$ of $n$ items. Every item $j$ has a profit $p_j$ and a size $s_j$. Further there is a capacity $c$ of the knapsack. The task is to choose a subset $A'$ of $A$, such that the total profit of $A'$ is maximized and the total size of $A'$ is at most $c$. The d-dimensional knapsack problem (d-KP) generalizes the knapsack problem by using items of sizes within a number $d$ of dimensions. Different techniques for solving hard problems were successfully applied to the knapsack problem. Among these are pseudo-polynomial algorithms, approximation algorithms, and integer programming. We used these results in order to show several parameterized algorithms and we try to improve the running times. Further we are working on polynomial time solutions for special knapsack instances.