1
$\begingroup$

Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for.

I have a problem with the following setup: I have a (finite) totally ordered set $(T, \leq)$ and a set of functions $f_i: T \to T$ that are non-increasing (i.e. $f_i(t) \leq t$). I know at least one point $t \in T$ but in general I only have access to $T$ via membership queries, that starting point, and the $f_i$.

I am looking for any point $t_{min}$ which is a simultaneous fixed point of all of the $f_i$. Obviously I can find this by just calculating $(f_1 \ldots f_n)^k(t)$ for our starting point $t \in T$ (note: This wouldn't be true if the $f_i$ could increase their argument).

My question is this: Given some (in general non-uniform, but I'd be happy for an answer that assumes the same cost for each as a starting point) cost model for the $f_i$, how do I find such a $t_{\min}$ with a small cost of reaching it in terms of total cost of the $f_i$ invocations to get to that point?

There are lots of obvious heuristics one can apply, but it's not obvious which ones are good, and of the ones I've tried whether they work well or not seems to depend massively on the shape of the problem and the effectiveness of individual $f_i$.

Anecdotally, in my particular use case, the following seem to usually be true:

  • Especially after a few iterations, most points are likely to be fixed points of most of the $f_i$.
  • It is much more likely that $f_i^2(s) = f_i(s)$ than that $f_j(f_i(s)) = f_i(s)$ for $j \neq i$.

Other things that might be helpful:

  • In my concrete use case, $T$ is a set of strings over some ordered alphabet, with $\leq$ being the shortlex order (i.e. $s \leq t$ if $|s| < |t|$ or $|s| = |t|$ and $s$ is lexicographically before $t$).
  • I can sample uniformly at random from $T$, and my initial $t$ comes from that distribution, but sampling is typically much more expensive than individual $f_i$ invocations.

Are there any good heuristics/metaheuristics I should be looking at for this class of problem?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.