1
$\begingroup$

I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $w_1\leq w_2\leq\cdots\leq w_n$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $j$ appears, place it into the bin with probability $p_j$ and ignore it otherwise.

$\endgroup$
  • $\begingroup$ Do you know $w_j$ before-hand, but not the order? if the answer is no, do you know the distribution from where they are sampled or at least a bound on the maximal value? Also, do you know the how many elements are? All this information is important to define the optimal strategy. I think there exists a deterministic strategy that maximize the expected value of the number of items placed into the bin, independently from the answer to all my previous questions, it is just that the strategy is conditioned on those answers. $\endgroup$ – Marcelo Fornet Jun 16 at 0:17
1
$\begingroup$

Well as you already noticed, or at least didn't mention, it is easy to see that there is no deterministic competitive Algorithm for your problem. (Counterexamples only need two items, and you can use the fact that the algorithm is deterministic.)

Your approach taking randomization actually isn't enough as some difficulties cannot be overcome by randomization. But there are a few relaxation models of your problem.

Some of those, and a few details to my answer can be found in the paper by Susanne Albers, Arindam Khan and Leon Ladewig named "Improved Online Algorithms for Knapsack and GAP in the Random Order Mode" (see section 1.1).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.