4
$\begingroup$

Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$ and $q_j$. Suppose that initially we have $n$ items of identical quality $q$, I want to obtain a final item of maximal quality, by a set of merging operations. How to find an optimal sequence of merging operations?

For example, if we have $4$ items, we can merge $1$ and $2$ to a new item $a$, $3$ and $4$ to a new item $b$, and then merge $a$ and $b$ to the final item; we can also merge $1$ and $2$ to item $a$ and then merge $a$ and $3$ to a new item and then merge it with $4$ to a final item. Has this problem been explored before mathematically?

Let me give two examples of $f$.

  1. $f(x,y)=\frac{xy}{xy+(1−x)(1−y)}$. This function is commutative and associative (as a binary operation) so the quality of the final merged item is independent of the merge sequence;

  2. $f(x,y)=\frac{10xy−(x+y)+1}{8xy−2(x+y)+5}$. In this case, what is the optimal merge sequence?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Is the only thing known of $f$ that it is increasing? $\endgroup$
    – Jukka Kohonen
    Commented May 30, 2022 at 4:56
  • $\begingroup$ @JukkaKohonen $f$ may have a complex form. As I am interested in solving the generic case, so I am not targeting a particular $f$. Let's assume that $f$ is increasing and, if that may help, concave in $q_i,q_j$. $\endgroup$
    – lchen
    Commented May 30, 2022 at 6:37
  • $\begingroup$ At each step, is the number of items reduced by only $1$? $\endgroup$
    – Rodrigo de Azevedo
    Commented May 30, 2022 at 9:58
  • $\begingroup$ @RodrigodeAzevedo Yes, each time we can merge 2 items into another item of better quality. If we choose to gradually merge all items, finally we will get a single item. Please refer to my comment of the answer below for more information on $f$. $\endgroup$
    – lchen
    Commented May 30, 2022 at 13:39
  • $\begingroup$ Semi-naive implementation (can be run online at tio.run/#python3-pypy ). There seem to be a variety of tree shapes obtained. $\endgroup$
    – Peter Taylor
    Commented May 31, 2022 at 8:28

1 Answer 1

Reset to default
1
$\begingroup$

This is only about the smallest nontrivial case $n=3$ but too long for a comment. Writing it here because it may help in thinking about the bigger cases.

If $n=3$, exact optimum is required, and $f$ is only known to be increasing and symmetric, it is not possible with less than exhaustive trial of all three possible merging trees.

Suppose $q_1=0.01$, $q_2=0.02$ and $q_3=0.03$, and further $$ q_{1,2} = f(0.01,0.02) = 0.1, \\ q_{1,3} = f(0.01,0.03) = 0.2, \\ q_{2,3} = f(0.02,0.03) = 0.3, $$ where $q_{i,j}$ is the quality obtained by merging $i$ and $j$.

Now there are three possible merging sequences (up to symmetry), and without further knowledge of $f$, it is not possible to know which one has the best quality: $$ q_{(1,2),3} = f(0.1, 0.03) = \;? \\ q_{(1,3),2} = f(0.2, 0.02) = \;? \\ q_{(2,3),1} = f(0.3, 0.01) = \;? \\ $$ By a suitable choice of an increasing function $f$, it is possible to choose any one of them to be the biggest.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Thank you for your response. Let me provide more information on $f$. We can assume that all the quality $q_i\in [a,1]$ with $a\in(0.5,1)$ being a threshold. $f(x,y)$ is symmetrical in $x$ and $y$ and concave in $x$ (and $y$). $f(x,1)=1$, $f(x,y)>x$ for $x\ge a$. Can we have some tractable insight? $\endgroup$
    – lchen
    Commented May 30, 2022 at 9:44
  • $\begingroup$ @lchen That helps a bit but not too much. What may really help is to know what your $f$ is (or to what parametric family it belongs, if it is a parametric family). Then one can play some games and, perhaps, come up with a meaningful answer. In full generality the problem is hardly tractable... $\endgroup$
    – fedja
    Commented May 30, 2022 at 15:03
  • $\begingroup$ @fedja Let me give two examples of $f$. (1) $f(x,y)=\frac{xy}{xy+(1-x)(1-y)}$. This function is abelian so the quality of the final merged item is independent of the merge sequence; (2) $f(x,y)=\frac{10xy-3(x+y)+1}{8xy-6(x+y)+5}$. In this case, what is the optimal merge sequence. $\endgroup$
    – lchen
    Commented May 31, 2022 at 2:46
  • $\begingroup$ @Ichen I guess you mean the first function is commutative and associative (as a binary operation) $\endgroup$
    – Jukka Kohonen
    Commented May 31, 2022 at 6:41
  • 1
    $\begingroup$ @lchen Also, I should say that while it is theoretically quite interesting, it is rather trivial in terms of programming: the corresponding maxima $m_n$ satisfy the recurrence relation $m_1=q$, $m_n=\max_{1\le k\le [n/2]}f(m_k,m_{n-k})$, which runs in time $n^2$. $\endgroup$
    – fedja
    Commented May 31, 2022 at 14:30

You must log in to answer this question.