2
$\begingroup$

We would need some suggestions for the proof of NP-hardness of an optimization problem.

The problem

$$ \max_{x_{a,s}} \sum_s \sum_a x_{a,s} q_a \lambda_s \prod_{s' < s} \prod_{a' \neq a} (1 + x_{a',s'} (c_{a'}-1) ) $$

\begin{align} \sum_{s \in S} x_{a,s} \leq 1 & \quad \forall a \in A \\ \sum_{a \in A} x_{a,s} \leq 1 & \quad \forall s \in S \\ x_{a,s} \in \{0,1\} & \quad \forall a \in A, s \in S \end{align}

The parameters have the following structure:

\begin{align*} c_a \in [0,1] & \quad \forall a \in A\\ \lambda_s \in [0,1] & \quad \forall s \in S\\ \lambda_s >\lambda_{s'} & \quad \forall s,s' \in S:s<s'\\ q_{a} \in[0,+\infty) & \quad \forall a \in A \end{align*}

In words: the problem requires one to assign the elements of $A$ to the elements of $S$ such that the value of each assignment is determined as follows

  • if an element $a$ is assigned to $s=1$, then the value of the assignment of this element is: $q_{a}\lambda_1$;
  • if an element $a$ is assigned to $s=2$, then the value of the assignment of this element is: $q_{a}\lambda_2 c_{a'}$ where $a'$ is assigned to $s=1$;
  • if an element $a$ is assigned to $s=3$, then the value of the assignment of this element is: $q_{a}\lambda_3 c_{a'} c_{a''}$ where $a'$ is assigned to $s=1$ and $a''$ is assigned to $s=2$;
  • and so on.

The total value of the assignment is given by the sum of the values of all the element assignments. So, with $|S|=3$, the total value is: $q_{a}\lambda_1 +q_{a}\lambda_2 c_{a'} + q_{a}\lambda_3 c_{a'} c_{a''}$.

The problem is easy (but we do not know whether it is hard in general) when:

  • $\lambda_s = 1$: the algorithm is based on dynamic programming starting from the last $s$ and going backward to the first

  • $c_a=1$: the algorithm is simple, being a greedy optimizer.

Question: any idea on how to find a reduction for proving the NP-hardness of the problem?

$\endgroup$
  • 3
    $\begingroup$ Why is your objective so complicated? Is this the standard assignment problem? $\endgroup$ – Austin Buchanan Sep 18 '13 at 17:13
  • $\begingroup$ No, our problem is not the standard assignment problem. The difference between a 2IAP (2-index assignment problem) and our problem is precisely in the objective function. In the former case the objective function is linear, in the latter it is not. $\endgroup$ – Guev Sep 19 '13 at 8:15
  • $\begingroup$ You have written a nonlinear objective, but maybe it can be rewritten as linear by substituting in new parameters. Can you describe where this objective came from? $\endgroup$ – Austin Buchanan Sep 19 '13 at 14:40
  • $\begingroup$ We have a set of objects $A$ that has to be allocated into an ordered set of positions $S$. We assume a user to scan the positions from the first to the last. Once the user gets a position, the probability that he stops depends on the position (probability \lambda_s) and on the specific object a allocated in such position (probability $c_a$). $\endgroup$ – Guev Sep 19 '13 at 19:19
  • $\begingroup$ Can you give motivation for your problem? $\endgroup$ – Austin Buchanan Sep 19 '13 at 20:55

Your Answer

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

Browse other questions tagged or ask your own question.