Re: Fault-tolerant telephone trees
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 3 Oct 2005 19:07:16 -0700
Andy Spragg wrote:
> I am membership secretary of a metal detecting club. Our outings are
> invariably and inevitably arranged at short notice (say three or four
> days), and all the members need to be alerted within that period of
> time. I have inherited a simple in-series system whereby the organizer
> alerts four people, each of whom then calls one new person each, and
> so on. This system does not work very well, because of people being
> out when phoned, or people who just aren't very reliable at passing on
> the message.
>
> I'm trying to design a better way of doing it, still based on
> telephone (less than half the members have email). It seems to me that
> by stipulating that each person should get and make two calls rather
> than one, it should be possible to design a solution which is much
> more efficient (greatly reduces the maximum number of calls anyone can
> be from the start) and fault-tolerant (because a missed or an unmade
> call does not cut off information flow).
The problem here is that the optimal solution is likely to look like
"have everyone try to call everyone else once they know", without a
cost function or limitations on who can call whom.
There's an incompatability between being "efficient" and being
"complete". If you want to have a solution where everyone is reached,
most everyone should call the people who are seldom at home. If you
want it to be "efficient", by minimizing the total number of phone
calls, then lots of calls to someone seldom at home will be wasted.
> It occurs to me that there will undoubtedly be a body of theory to
> call upon (indeed, for the modest numbers of nodes I have to deal
> with, there may well be an optimum solution already documented). Could
> someone point me in the right direction please? Many thanks,
Random graph theory, specifically the problem where you have a graph
(which represents who can call whom), and each vertex v has a
probability p(v) of existing; then you're supposed to minimize the
radius of the resulting graph. This differs from the "standard random
graph model", where every edge uv has a probability of being in the
graph or not being in it.
I suspect, though, that with this modification, the optimal solution
will still be trivial, i.e., "have everyone try to call person P with
probability p(P), for all P", where p(P) depends only on the
probability that P is at home.
--- Christopher Heckman
.
- Prev by Date: 3rd Experiment |OR| Infinity
- Next by Date: Re: Tricky Math Problem - Phones
- Previous by thread: 3rd Experiment |OR| Infinity
- Next by thread: Re: real valued function
- Index(es):
Relevant Pages
|
