Arbeitsgruppe Algorithmen und Komplexität

Research Interests

  • Faster approximation schemes for linear and convex programming (including maximum flow, minimum cost flow, minimum fractional bin packing)
  • Efficient polynomial time approximation schemes (EPTAS) for different optimization problems (e.g. scheduling and knapsack problems) with focus on running time. Lower bounds on the running time of approximation schemes (using complexity theoretical assumptions)
  • Algorithm engineering for approximation algorithms and approximation schemes (design, analysis, implementation and experiments)
  • Design of approximation algorithms with improved approximation ratio for 2D and 3D packing problems (e.g. 2D knapsack, 2D bin packing and 2D strip packing) and other combinatorial optimization problems (e.g. bin packing, scheduling on unrelated machines)
  • Design of robust online algorithms with focus on small migration factors and fast running time (e.g. for scheduling on identical and uniform processors and bin packing)
  • Design of robust approximation algorithms for classical optimization problems (e.g. linear optimization. knapsack, and scheduling problems) that work also under uncertain data; including modeling of robustness and modification of solutions
  • Algorithms for practical applications in logistics and production planning
  • Algorithms for practical applications in grid-computing, multi-core scheduling and communication networks