Campus Event Calendar
Event Entry
What and Who
How to Pack Your Items When You Have to Buy Your Knapsack
Sebastian Ott
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 20 August 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We consider a generalization of the classical knapsack problem. While in the standard setting a fixed capacity may not be exceeded by the weight of the chosen items, we replace this hard constraint by a weight-dependent cost function. The objective is to maximize the total profit of the chosen items minus the cost induced by their total weight. In my talk I will focus on convex cost functions and present an FPTAS and a fast 2-approximation algorithm for this setting.
Contact
Sebastian Ott
--email hidden
passcode not visible
logged in users only
Sebastian Ott, 07/10/2013 15:29 -- Created document.