Problem. Let $x = (x_1,\dots,x_N) \in K^{N}$, i.e., each element $x_i$ can take at most $K$ discrete values. Let $x_{(i)}$, for $i \in \{1,\dots,I \}$ possible overlapping subsets of $x$. For example, for $K = 2$, $N= 3$, and $I = 2$ we may have $x_{(1)} = (x_1,x_2)$ and $x_{(2)} = (x_2,x_3)$.
Consider the following problem:
$$ \min_{x\in K^{N}} \frac{\sum\limits_{i\in [I]} f_i(x_{(i)})}{\left(\sum\limits_{i\in [I]} g_i(x_{(i)})\right)^2},$$
where each of the $f_i(x_{(i)})$ is positive, and $\sum_{i\in [I]} g_i(x_{(i)}) >0$, however some of the $g_i(x_{(i)})$ can be negative. I could not find any resource that treated this integer problem in a distributed manner or even in a centralized manner.
Question. Has anyone seen a similar problem or has any idea on how to solve this problem distributedly (similarly, for example, to the max-sum algorithm)?
Attempts. I have tried to simplify or approximate the problem to put it in a standard distributed optimization form as
$$ \min_{x\in K^{N}}\sum_{i \in [I]} h_i(x_{(i)}),$$
which can be solved in many ways by distributed algorithms. For example, if the $g(x_{(i)})$ were to be strictly positive, we could have an upper bound on the value of this problem
$$ \min_{x\in K^{N}} \frac{\sum_{i\in [I]} f_i(x_{(i)})}{(\sum_{i\in [I]} g_i(x_{(i)}))^2} \leq \min_{x\in K^{N}} \frac{\sum_{i\in [I]} f_i(x_{(i)})}{\sum_{i\in [I]} g_i(x_{(i)})^2} \leq \min_{x\in K^{N}} \sum_{i\in [I]}\frac{f_i(x_{(i)})}{ g_i(x_{(i)})^2},$$
However, this is not the case, unfortunately. Is there any other trick that I could use to at least approximate the problem?
Resources. The closest related work I could find is this paper in which the objective is a function of sums, although it's only for continuous variables.
