The first fixpoint of x → ∑_i=1^k ⌈x/a_i ⌉ × b_i+c

Let

where a_i, b_i and c are positive integer values. We look for the smallest fixpoint of f if it exists, i.e., the smallest x^* such that f(x^*) = x^*.

OPEN QUESTION: Is there a polynomial (in the input size) algorithm to compute x^* ?

Hadrien Cambazard (LINA, Nantes) has introduced this problem to me. It plays an important role for people working on real time problems.

• Note that It is easy to design a pseudopolynomial time algorithm for this problem (think about it)
• It is also easy to check that there is a solution iff ∑_i b_i/a_i < 1
• I have a simple algorithm to compute a fixpoint (not the smallest one) in polynomial time (see below)

A polynomial algorithm to compute a fixpoint (not the smallest one)

The size D of the interval where to search for x^* is then

We can perform a dichotomic search. As for each candidate x, we have to compare x to f(x) this leads to an overall time complexity of O(k logD).

If D ≤ ∏_{i ≤ k} a_i, we have an O(k² loga_max) algorithm (where a_max is the larges a_i). This is polynomial in the input size.

Now assume that D > ∏_{i ≤ k} a_i. Note that ∀ x, f(x + ∏_{i ≤ k} a_i) = f(x) + ∏_{i ≤ k} a_i ∑_{i≤ k} b_i/a_i. Now let q be the largest integer such that f(q ∏_{i ≤ k} a_i) ≤ q ∏_{i ≤ k} a_i, i.e.,

Which means

Now we look for x^* between q ∏_{i ≤ k} a_i and (q+1) ∏_{i ≤ k} a_i. The size of this interval is less than D and hence we have the same O(k² loga_max) algorithm.

This document was translated from L^AT_EX by H^EV^EA.