1
$\begingroup$

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})} $$

Contour plot

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Mat Jul 20 '18 at 16:52
  • $\begingroup$ 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). $\endgroup$ – usMath Jul 20 '18 at 19:05
  • $\begingroup$ 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. $\endgroup$ – Mat Jul 20 '18 at 19:09
  • $\begingroup$ The global maximum happens at i = 5 on the set Q = {100, 101, 102, 103, 104, 105}. This is Q[1] 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. $\endgroup$ – usMath Jul 20 '18 at 19:29
  • $\begingroup$ 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 $\endgroup$ – Mat Jul 20 '18 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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