1
$\begingroup$

I am trying to prove whether the following problem is NP-hard or not:

Items with a certain length arrive in a fixed sequence and must be assigned to one of two containers which are constrained in terms of length. The containers are not identical but have different length constraints. Our objective is to maximize the total number of items in both containers. This problem is not really a knapsack problem, because we are not allowed to skip items. The problem is also not exactly a scheduling problem (in which the containers would be two parallel machines and we are assigning a fixed queue of jobs to machines) because we do not want to minimize completion time but want to maximize the number of completed jobs.

I have done some extensive literature review of "Precedence constrained knapsack problems" and "Complexity of Scheduling under Precedence Constraints" but could not yet find this exact type of problem. Most similar problems are indeed NP-hard, so I think this one is as well.

I would appreciate any hints to other literature or tips on how I could prove NP-hardness (or not), e.g. reduction from partitioning / ...

$\endgroup$
2

2 Answers 2

1
$\begingroup$

I think your problem is exactly the scheduling problem: $$Q2|\bar {d_i} = d|\sum U_i$$ which is a particular case of the more general scheduling problem: $$Q2||\sum u_i U_i$$

which according to the table at Complexity results for scheduling problems / Parallel machine problems without preemption is maximal pseudo-polynomially solvable, with reference the survey paper:

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys.

Sequencing and Scheduling: Algorithms and Complexity, volume 4 of Operations Research and Management Science.

CWI, Amsterdam, 1989.


To understand that your problem is $Q2|\bar {d_i} = d|\sum U_i$, note that "the two machines have two different maximum lengths $L_1$ and $L_2$" is equivalent to "all jobs have the same deadline, but jobs are completed $L_1/L_2$ faster when run on the second machine". Notation $Q2$ means that there are two uniform machines, ie the two machines can have different speeds but job processing times are proportional on the two machines. Notation $\bar {d_i} = d$ means all job have the same deadline. The objective $\sum U_i$ is the number of completed jobs.

$\endgroup$
3
  • $\begingroup$ Thank you for this answer! The way I understand the paper, if the machines are unrelated, not uniform, the problem becomes NP-hard? The table does not include unrelated machines, but the Paper by Lawler / Lenstra makes me think so. $\endgroup$
    – Christian
    Commented Dec 7, 2023 at 7:27
  • $\begingroup$ Or rather: if the machines are unrelated, it can not be solved in pseudo-polynomial time $\endgroup$
    – Christian
    Commented Dec 7, 2023 at 7:42
  • $\begingroup$ Also does your answer consider precedences between the items? $\endgroup$
    – Christian
    Commented Dec 7, 2023 at 7:48
1
$\begingroup$

It is NP-hard. Below is a reduction from the subset sum problem.

The subset sum problem with positive inputs asks for a list of positive integers $a_1,\dots,a_n$ whether a subset of them has the sum $M$.

Assume we have an oracle for your problem such that $f(L_1,L_2,a_1,\dots,a_n)$ outputs the maximum number of consecutive items from $a_1,\dots,a_n$ which we can fit in containers of sizes $L_1$ and $L_2$. Then checking whether $f(M,\ M-\sum_{i=1}^n a_i,\ a_1,\dots,a_n) = n$ answers the corresponding subset sum problem. This is because we chose the lengths such that all space must be used, so we can only fit all $n$ elements if there is a subset with sum $M$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .