1
$\begingroup$

The problem comes from network coding area. There is a wireless server that holds a set of data packets. There is a set of receivers, each already possesses a subset of the data packets, and wants all the remaining data packets. The server would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...

Update: Thanks a lot for your attention and kindness to a newbie. Below is a more detailed version of my problem.

Original system model: we perform an iterative operation on a hyper-graph $\mathcal H(\mathcal V, \mathcal E)$: In each iteration, we use one color to color $\mathcal H$ in a way that at most one vertex $v$ of each hyper-edge $e$ is colored. (a.k.a. strong coloring). We then remove these vertices from $\mathcal H$.

Question-1: what is the optimal strong coloring solution for each iteration, so that the number of iterations is minimized?

We have proved that this question is NP-hard to answer.

Now consider the following system model:

New system model: The same iterative strong coloring and removal process as above. However, when we try to remove a vertex, it has a nonzero probability of staying at each hyper-edge it belongs to. If it successfully stays at at least one hyper-edge, it will be uncolored, and will enter the next iteration. (When this happens, the vertex is only removed from some but not all the hyper-edges it belongs to.)

Question-2: What is the optimal strong coloring solution for each iteration, so that the expected number of iterations is minimized?

I conjecture that this question is also NP-hard to answer, but have no clue on how to prove it.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Can you specify the problem? Your question seems impossible to answer without knowing more about the prso ken you’re considering. $\endgroup$
    – Robin Houston
    Sep 28, 2017 at 7:52
  • $\begingroup$ (Sorry for the bizarre autocorrecto in my comment above, which I can no longer edit.) $\endgroup$
    – Robin Houston
    Sep 28, 2017 at 8:20
  • 1
    $\begingroup$ Doesn't your second case contain the first one, i.e. it is possible that exactly $0$ packets get lost? In this case, an efficient algorithm for the second case should also work when nothing is lost, thus in the NP-hard case... $\endgroup$
    – Dirk
    Sep 28, 2017 at 8:28
  • $\begingroup$ The original problem sounds like the multiple knapsack problem. Can you confirm this is the case? If that is the case can we assume we miss knapsacks (and all items in them) randomly? $\endgroup$
    – zen
    Sep 28, 2017 at 13:30
  • $\begingroup$ @RobinHouston thanks a lot for your attention and kindness to a newbie. Please kindly refer to my clarified and concrete problem. $\endgroup$
    – fishermanymc
    Sep 29, 2017 at 12:22

0

Reset to default

Browse other questions tagged or ask your own question.