# Optimizing an Algorithm for Timestamp-Aware Partitioning of Data

## My Problem

I'm currently dealing with an algorithmic problem that involves two input lists:

1. A list of natural numbers $$[A_1, A_2, \dots, A_n]$$ with $$A_1, \dots, A_n \in \mathbb{N}$$.
2. A list of triples $$[(B_1, C_1, D_1), (B_2, C_2, D_2), \dots, (B_m, C_m, D_m)]$$ with $$m\geq n$$, natural numbers $$B_1, \dots, B_m \in \mathbb{N}$$, attributes $$C_1, \dots, C_m$$ and timestamps $$D_1, \dots, D_m$$.

Let $$\mathcal{X}$$ represent the set of triples in the second list. My objective is to find a partition $$(\mathcal{P}_1, \dots, \mathcal{P}_n)$$ of $$\mathcal{X}$$ that satisfies the following conditions:

1. The sum of natural numbers in the $$i$$-th partition must equal $$A_i$$. In other words, $$\sum_{(B,C,D) \in \mathcal{P}_i} B = A_i$$ for all $$i = 1, \dots, n$$.
2. Only triples sharing the same attribute $$C$$ should be placed in the same set within the partition. This means that for all $$i\in 1,\dots, n$$, there exists some $$c_i$$ such that $$C = c_i$$ for all $$(B,C,D) \in \mathcal{P}_i$$.
3. Among all partitions satisfying condition 1 and 2, we aim to minimize the timestamp difference within the sets of the partition. To formalize this, let's denote the time difference between two timestamps $$D$$ and $$D^\prime$$ as $$d(D, D^\prime)$$. Our goal is to minimize the following expression

$$\sum_{i=1,\dots, n} \max_{(B,C,D), (B^\prime, C^\prime, D^\prime) \in \mathcal{P}_i} d(D, D^\prime).$$

We can assume that a solution exists.

## My Approach and Objective

So far, I've developed an algorithm that involves exploring various combinations of partitions while minimizing the number of operations required to verify whether a partition is promising. I've dedicated a significant amount of time in search of a more sophisticated algorithm that doesn't rely on trying every combination sequentially.

I'm looking for assistance and guidance in finding a faster algorithm. Any insights or suggestions would be greatly appreciated. :)

• You can group the triples based on the attributes and solve each group separately Commented Nov 6, 2023 at 18:33
• @CommandMaster That's a great suggestion! We still need to determine how to assign each group to a number from the first list. However, given that I'm working with a dataset where there are numerous groups, and each group is relatively small, this approach seems quite promising. Commented Nov 7, 2023 at 7:10