Is there an efficient algorithm to this problem? Let f <mrow class="MJX-TeXAtom-ORD"

Lucia Grimes

Lucia Grimes

Answered question

2022-07-15

Is there an efficient algorithm to this problem?
Let f i be n strictly decreasing, continuous functions on the positive real numbers with lim x 0 f i = .
Let I be a positive real number.
I think I can prove that there always exists a unique set of n non-negative xi that sum to I and that have: f i ( x i ) = f j ( x j ) for all i, j in 1, ..., n.
I think the greedy algorithm gives a solution to this problem, but is there anything better? In particular, is there a closed solution?

Answer & Explanation

Dobermann82

Dobermann82

Beginner2022-07-16Added 15 answers

Step 1
I don't think you can use theg reedy algo here. A fairly simple way of doing it is by using the inverse functions.
If you know the inverse functions, you can apply a root finding/minimization algo for:
I = i = 1 n x i = i = 1 n f i 1 ( y ) I i = 1 n | f i 1 ( y ) | = 0
Step 2
If you don't know the inverse, you can get the inverse values by an extra root finding/minimization for each of the functions in the form of | f i ( x i ) y | = 0

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?