Re: asymptotic behaviour of multivariate recurrence equations?

"Marc Nunkesser" <marc.nunkesser@xxxxxxxxxxx> writes:

> I am interested in exponential algorithms and currently I am playing
> around with (bounded) search trees. Often such an approach leads to
> homogeneous linear recurrences in a single variable. For these it is
> enough to compute the real root of its characteristic polynomial
> with max absolute value and we know the basis of the asymptotic
> behaviour.
>
> Now what happens with multivariate recurrence equations?

If your problem becomes easy when any of the variable reaches zero (as
in your case), then you can get an upper bound by using appropriate
weights for each variable to get a univariate recurrence. David
Eppstein's paper "Quasiconvex Analysis of Backtracking Algorithms"
describes one method to find optimal weights, but the problem seems to
be well-behaved numerically, so any method will probably work. See
Fomin, Grandoni & Kratsch: "Measure and Conquer: Domination - A Case
Study", ICALP'05 for a recent application of this kind of analysis;
they use random local search to find the weights.

--
Falk
.