1
$\begingroup$

I'm trying to figure out if there is a common name for the following optimization problem of computing products of subsequences of a sequence:

Given a set $S$ of $m$ sets $\{S_1,\dots, S_m\}$, where $S_i = \{j_0, \dots, j_{k_i}\}$ s.t. each $j_\ell$ is an index i.e. $0\leq j_\ell \leq n$, and a sequence of elements $X = (x_0,\dots, x_n)$, find the minimal number of multiplications it will take to compute all sets, assuming that for computing each set $S_i$ we need to multiply all elements with the corresponding indices i.e. $X(S_i) = \prod_{j \in S_i} x_j$.

For example, suppose we have $S= \{S_1,S_2,S_3,S_4\}$:

$S_1 = \{0,1,3,4\} \\ S_2 = \{0,1,2,3,4\} \\S_3 = \{0,1,2,5,6\}\\ S_4 = \{0,1,3,4,5,6\}$

The minimal number of multiplications will be $8$ (as far as I can tell):

$y_1 =x_0x_1\\ y_2 = y_1x_2\\ y_3 =x_3x_4\\ y_4 = x_5x_6\\ X(S_1) = y_1y_3\\ X(S_2) = y_2y_3\\ X(S_3) = y_2y_4\\ X(S_4) = X(S_1)y_4$

It's not exactly a set cover problem, though it's very similar. Generalized matrix chain multiplication is close too, seems even a better fit than the set cover, but maybe there is something else. I was wondering if some problem in graphs might be a better match.

Do you have any idea, what this problem might be called? Or to which one is it the closest?

$\endgroup$
2
$\begingroup$

Not sure if this problem has a name, but you can solve it via integer linear programming as follows, where I have changed the meaning of $S$, $x$, and $y$. For each subset $S \subseteq \{0,\dots,6\}$, let binary decision variable $x_S$ indicate whether subset $S$ is formed. The problem is to minimize $\sum\limits_{S:|S|>1} x_S$ subject to \begin{align} x_S &= 1 &&\text{for the (four) target subsets $S$} \tag1\\ x_S &\le \sum_{\emptyset \not= T \subsetneq S} x_T x_{S \setminus T} &&\text{for all $S$ such that $|S|>1$} \tag2 \end{align} Constraint $(1)$ forces the formation of the specified target subsets. Constraint $(2)$ forces each formed subset to arise from the disjoint union of two other proper subsets. You can linearize this constraint by introducing a new binary variable $y_{T,S \setminus T}$ and replacing $(2)$ with \begin{align} x_S &\le \sum_{\emptyset \not= T \subsetneq S} y_{T,S \setminus T} &&\text{for all $S$ such that $|S|>1$} \tag{2a} \\ y_{T,S \setminus T} &\le x_T &&\text{for all $S$ and $T$ such that $\emptyset \not= T \subsetneq S$ and $|S|>1$} \tag{2b} \\ y_{T,S \setminus T} &\le x_{S \setminus T} &&\text{for all $S$ and $T$ such that $\emptyset \not= T \subsetneq S$ and $|S|>1$} \tag{2c} \end{align} For your four target sets, the optimal objective value is indeed $8$, attained by taking $x_S = 1$ for all $S$ with $|S|\le 1$, $$x_{01}=x_{34}=x_{56}=x_{0156}=x_{0134}=x_{01234}=x_{01256}=x_{013456}=1,$$ and all other $x_S=0$.

In terms of graph theory, you can interpret $x_S$ as a node variable and $y_{T,S \setminus T}$ as an edge variable in an undirected graph. The problem seems like a generalization of minimum edge cover for which only the target nodes need to be covered.

$\endgroup$
1
  • $\begingroup$ thanks, a generalization of minimum edge cover seems to be a good fit $\endgroup$ – pintor Mar 12 at 8:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.