1
$\begingroup$

Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements $x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is sorted if $x_i \leq x_{i+1}$ and $y_i \leq y_{i+1}$ for all $i \in [n-1]$. Sorting $X$ is not always possible for instance if the given input has two tuples $(x_i,y_i), (x_j,y_j)$ such that $x_i > x_j $ and $y_i < y_j$ for some $i \neq j$. So we want to merge tuples in $X$ so that the resulting collection is sorted and the merge operation $\phi(i,j,k)$ is defined as

$$\phi(i,j,k) := \Big\{\text{delete}~(x_i,y_i), (x_j,y_j)~\text{from}~X~\text{and insert}~\big(\frac{x_i+x_j}{2}, \frac{y_i+y_j}{2}\big)~\text{at position}~k\big\}$$

The problem always has an obvious solution with $(n-1)$ merge operations i.e, merging everything to a single tuple is always feasible. But we would like to find the minimum number of merge operations required to sort the collection.

Even though we suspect that finding the minimum number of merge operations is NP-hard, we do not have a hardness proof to support the claim. The problem looks like something which might have been already studied in the literature. If you are aware of any related or similar problems please guide us to relevant results. Any clues for hardness or algorithmic results are helpful.

Example: Given $X=\{(1,4),(2,2),(3,2),(4,1)\}$ with two merge operations i.e, $\phi(1,4,3)$ followed by $\phi(2,3,2)$ we can obtain $\{(2.5,2),(2.5,2.5)\}$, which is sorted.

$$\{(1,4),(2,2),(3,2),(4,1)\} \xrightarrow[]{\phi(1,4,3)} \{(2,2),(3,2),(2.5,2.5)\}$$ $$\{(2,2),(3,2),(2.5,2.5)\} \xrightarrow[]{\phi(2,3,2)} \{(2,2),(2.5,2.25)\}$$

Note-1: $\phi(i,i,k)$ is a valid operation.

Note-2: While inserting an element at some index $\ell$, the index of tuples at positions $\{\ell,\dots,n\}$ are incremented by $1$, i.e, no element in the collection is deleted while inserting.

Note-3: If the merge operation is restricted to operations of the form $\phi(i,i+1,i)$ and insert the resulting element at position $i$, then the minimum number of operations can be found in polynomial time using a dynamic programming algorithm.

Thanks in advance.

$\endgroup$
8
  • $\begingroup$ I wonder how you can solve $\phi(i, i+1, i)$ using dynamic programming. I guess you try to solve some problem on every segment (a la matrix chain multiplication problem), but the problem is that depending on the order you get different resulting tuple. $\endgroup$
    – Dmitry
    Dec 5, 2022 at 15:37
  • $\begingroup$ Is $\phi(i, i, k)$ a valid operation? $\endgroup$ Dec 5, 2022 at 16:59
  • 2
    $\begingroup$ I'm confused by allowing us to choose $k$. Does that mean we can overwrite and delete some other existing element of $X$? For instance, is $\phi(10,11,5)$ a legal operation? I suspect that there should be no $k$, and you are allowed to delete the pairs at $i,j$ and then append/insert the new pair. $\endgroup$
    – D.W.
    Dec 5, 2022 at 19:49
  • 1
    $\begingroup$ How can you say that the optimal will avoid $\phi(i, i, k) $? What about $X=\{(2,2),(1,2)\} $? Is merge rearrange the only allowed operation? If not then @D.W. might be right that $k$ is not needed in $\phi() $ $\endgroup$
    – Russel
    Dec 5, 2022 at 23:41
  • 2
    $\begingroup$ The order of the integers in the collection doesn't seem to matter. I think you should specify the collection as a set (not list), and have the $\phi$ operation delete two pair and inserts another pair. $\endgroup$
    – D.W.
    Dec 6, 2022 at 20:03

1 Answer 1

0
$\begingroup$

A crude estimate is that the worst number of merges is greater or equal to $\frac{n-1}{4}$. For this, consider the set \begin{equation} X=\{(0,1),\ldots,(0,m)\}\cup\{(1, 0),\ldots,(m, 0)\} \end{equation} where $m = \lfloor n/2\rfloor$. None of the points of the first list is comparable to any of the points of the second list. It means that if one of the points is untouched by the merging operations, then all the points of the other list must be touched by at least one merge operation. As each merge operation involves two points, it means that there are at least $\lceil m/2 \rceil$ merge operations. But $\lceil \lfloor n/2\rfloor /2\rceil\ge \frac{n-1}{4}$.

One can even reach a lower bound of $\frac{n-1}{2}$ by considering a set \begin{equation} X = \{(a_1, -a_1), \ldots, (a_n, -a_n)\} \end{equation} where $a_1,\ldots,a_n$ are distinct real numbers. Pairs of points in $X$ are never comparable, which means that $n-1$ of them must take part in a merge operation. Hence there are at least $\frac{n-1}{2}$ merge operations.

If we add more conditions on the $a_k$ s, for example assuming that they are independent over ${\mathbb Q}$, we have an exemple where $n-1$ merge operations are actually necessary because the points $(x, y)$ generated by the merge operations will always have the form $(x, -x)$ and they will always be distinct. They will never become comparable and the algorithm can stop only when the cardinality of $X$ is $1$, that is to say after $n-1$ operations.

$\endgroup$

Your Answer

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

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