# Is there a name for this problem or any close problem?

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?

## 1 Answer

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.

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