Campus Event Calendar
Event Entry
What and Who
Approximating the Orthogonal Knapsack Problem for Hypercubes
Rolf Harren
Uni Dortmund
Talk
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 29 May 2006
14:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
Given a list of d-dimensional cuboid items with associated profits,
the orthogonal knapsack problem asks for a packing of a selection
with maximal profit into the unit cube. We restrict the items to
hypercube shapes and derive a (5/4 + epsilon) for the two-dimensional
case, i.e., square packing. In a second step we generalize our
result to a ((2^d+1)/2^d + epsilon)-approximation for d-dimensional
packing.
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Benjamin Doerr, 05/21/2006 21:41
Benjamin Doerr, 05/21/2006 21:40 -- Created document.
Benjamin Doerr, 05/21/2006 21:40 -- Created document.