Optimisation problems with minimum quantity constraints Event as iCalendar

18 March 2015

2 - 3pm

Venue: Room 439.201

Location: Level 2, UniServices House, 70 Symonds Street

Host: Dr Richard Clarke

Contact email: rj.clarke@auckland.ac.nz

 

A Department of Engineering Science research seminar by Clemens Thielen of the University of Kaiserslautern, Germany.

 

Abstract:

An important aspect of resource efficiency is achieving a sufficient utilisation of resources that are used within a production process. This motivates to study optimisation problems in which a minimum amount of load is guaranteed for each resource that is used in a solution. One way to reach this goal is to specify a minimum quantity for the use of each resource, which means that, in any feasible solution, the utilisation of the resource is either zero or at least the given minimum quantity. In order to give an impression of the algorithmic consequences of such minimum quantity constraints on combinatorial optimisation problems, we summarise some of our recent results that show how minimum quantity constraints influence the complexity and approximability of network flow problems and packing problems, which are two important problem classes in combinatorial optimisation.