# Subset optimization with composite aggregate functions

I have a finite set $P = \{1, 5, 3, 6, 4, ..., p_n\}$ of size $N$ and average $A$.

I want to find the most efficient way to maximize the following function:

$$f(x, y) = \frac{1}{(1+e^{-6(x-2)})(1+e^{-6(y-2)})(1+e^{-0.1x-0.3y+1.5})}$$ where:

• $S \subsetneq P$;
• $x = |S|$;
• $y = \frac{min(S)}{A}$.

I really have no idea where to start other than sorting $P$. I'm looking for optimal time complexity or at least something considerably better than bruteforcing.

The conflicting extreme ideas are:

1. Taking a subset with $|S| = 1$ where the only element is $s = max(P)$. This will maximize the $y$ part but minimize the $x$ part.

2. Taking a subset with $|S| = N-1$ where the element that's excluded is $s = min(P)$. This will maximize the $x$ part but minimize the $y$ part.

## 1 Answer

If the set is unsorted, a time complexity of $O(N\log(N)$) is the best we can do, as that is the time complexity of sorting a list.

Let $Q$ be $P$ after it is sorted. We can consider $N-1$ cases.

For each case $1 ≤ i ≤ N-1$, let $S$ be the subset consisting of the last $i$ elements of the sorted set $Q$. Then:

$x = |S| = i$

$y = min(S)/A = Q[N-i]/A$

$f(x, y)$ would be evaluated $N-1$ times, for a time complexity of $O(N)$.

Since the slowest part of this process is $O(N\log(N))$, that is the time complexity of the overall process. The longest part of this would be sorting the list; calculating the maximum would be faster for large values of $N$.

If the set was presorted, this solution would have a $O(N)$ time complexity.

This solution is the optimal solution because $f(x, y)$ increases as $x$ increases or $y$ increases. A proper subset $S$ with a minimum value $M$ that does not contain all the values of $Q$ greater than or equal to $M$ could have the calculated $x$ value increased by including those values greater than or equal to $M$. As there are $N-1$ possible minimum values to consider, a time complexity of $O(N)$ is the fastest possible for this part of the solution.

• Nice explanation ! Most elements there I managed to find too, so it kind of confirms my own conclusions. However, could you check the smaller possible optimisations ? I'd really like to have this be the fastest. I'm thinking like doing 1 ≤ i ≤ (N-1)/2, and y could be P[i]/A, which bypasses creating any subset. Thoughts ? – Mat Jul 20 '18 at 16:52
• Thank you! I think that all values of i must be checked since the maximum can be anywhere in the set. For example, the set Q = {100, 101, 102, 103, 104, 105} has the maximum at i = 5. I agree that y should be Q[i]/A (edited the solution to add that). – usMath Jul 20 '18 at 19:05
• What I mean is if you start at i=Q[N-1], the max element, and go down, you must find the global maximum before reaching Q[N/2]. Correct me if I'm wrong. – Mat Jul 20 '18 at 19:09
• The global maximum happens at i = 5 on the set Q = {100, 101, 102, 103, 104, 105}. This is Q which happens after Q[N/2]. Other sets include sets of identical elements. However, I've noticed that the all sets I've looked at so far produces values of f with a negative second derivative, so once f starts decreasing, the maximum is likely to have been found. – usMath Jul 20 '18 at 19:29
• When you say i=5 is the maximum you mean that S=Q ? i starts at 0, and there are 6 elements in your set – Mat Jul 20 '18 at 19:33