I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is a much simpler setting where showing hardness should be easier. Please let me know if I should amend the original question instead.

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. We will restrict $G$ to be a cycle where every vertex has degree $2$ (and $m = n$).

The challenge is to assign weights $w_e$ to each edge to maximize the objective function $E = \sum_{e = \{i,j\}} w_e \Pr[X_i + X_j \geq w_e]$ where $\Pr[X_i + X_j \geq w_e]$ denotes the probability that that the sum of values taken by vertex $i$ and $j$ is greater than $w_e$. The additional constraint is that the weights $w_e$ need to be sub-additive, i.e., for any two edges $e'$ and $e''$ that "cover" edge $e$ meaning $e'$ and $e''$ include the vertices that make $e$, it holds that $w_e \leq w_{e'} + w_{e''}$.

Observe that the deterministic version where $p_i = 1$ is trivial. Any suggestions on possible directions for hardness or PTIME algorithm would be very helpful!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.