AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

In this talk the problem of selecting p items out of n available to minimize the total cost will be discussed. This problem is a special case of many important combinatorial optimization problems such as 0-1 knapsack, minimum assignment, single machine scheduling, minimum matroid base or resource allocation. It is assumed that the item costs are uncertain and they are specified as a scenario set containing K distinct cost scenarios. In order to choose a solution the min-max criteria is applied. The considered problem is not approximable within any constant factor unless P=NP. We provide a deterministic approximation algorithm with performance ratio of O(lnK), which strengthens the results known up to date.

Andreas Wiese

--email hidden

passcode not visible

logged in users only