Given this sort of dataset:

ID Score1 P1 Flag
id1 0.01 0.2 False
id2 0.99 0.9 True
... ... ... ...

The limitations of each variable are:

  • ID: identifier if each object, unique in the table
  • Score1: A number between 0 and 1, that represent the value of the object
  • P1: probability of call, betwen 0 and 1
  • Flag: should the object be in group <b?

I want to split the dataset in 2 groups (A and B) given the rules:

  • The sum of P1 on group A should be at least n
  • The sum of P1 on group B should be at least m
  • The diference between the average Score1 in the two groups should be minimal
  • The average of Score1 on all the selected (group A + group B) should be maximum
  • We don't have to select all the rows
  • Rows with Flag = True can not be in group A

How can I do this in a smart/fast way?


1 Answer 1


There is no efficient algorithm to do what you want, unless P=NP. In fact, there is no efficient algorithm to even decide whether a feasible partition of the dataset into two groups exists.

You can see this by reducing from the partition problem: Given a (multi-)set of positive numbers $X=\{x_1, x_2, \dots, x_n\}$ we want to decide whether there exists a subsets $S$ of $X$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$. Without loss of generality we can assume that $0 < x_i \le 1$ (by simply dividing all $x_i$ by $\max_{i=1, \dots, n} x_i$).

Then, for each $x_i \in X$ you can create a row in your dataset with:

  • ID = $i$;
  • Score = $0$;
  • P1 = $x_i$;
  • Flag = false.

Finally, pick $n = m = \frac{1}{2}\sum_{x \in X} x$.

A feasible parition into two groups $A$ a and $B$ induces a subset $S$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$. Specifically if $i_1, i_2, \dots, i_k$ are the IDs of the rows selected into $A$, you can define $S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$.

Conversely, given a set $S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$ such that $\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$, you can select $A$ as the set of rows with IDs in $\{i_1, i_2, \dots, i_k\}$ and $B$ as the set of rows not in $A$.


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.