For the n^-2 case, a beautiful aperiodic solution is to visit house gcd(a, b) at time t, where T(a) is the largest triangular number below t, and b = t - T(a). Best wishes, Adam P. Goucher
Sent: Saturday, March 17, 2018 at 4:53 PM From: "Michael Kleber" <michael.kleber@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Deterministic scheduling of Zipf's Law visits ?
This sounds like a problem for Jim Propp's de-randomization tricks -- converting a random method that has the right asymptotic distribution to a deterministic method that approximates its behavior. But I don't know what the random method with Zipfian distribution would be.
--Michael
On Sat, Mar 17, 2018 at 11:07 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Suppose that I'm a Fedex driver and I have N houses to visit, but only exactly 1 house every day (i.e., this is NOT a route planning problem). Since I'm an unimaginative Fedex driver, it's simply easier to go to the houses in the same order every cycle of days, whether or not I have something to deliver.
I'd like to come up with a *simple* house visit scheduling algorithm with the following properties:
* For each N, the output is a *fixed* *cyclic* schedule; i.e., after some # of days the entire schedule repeats; we'd like the cycle length to be relatively short and will accept some amount of deviation from Zipf's Law in return
* The % of visits to house #i in each cycle is very roughly proportional to 1/i
* Ideally, the deliveries to house #i should be spread out as much as possible -- i.e., not all bunched together on successive days
* The schedule for N+1 houses is simply computed from the schedule for N houses (alternatively, the schedule for N is computed from an a priori fixed number of schedules from smaller N's)
Here's an example of what NOT to do for Zipf's Law:
Suppose we have 4 houses, with visits scheduled like so:
1 1 2 1 2 3 1 2 3 4
Thus, we have 10 total visits each cycle, but the ratios are 40%, 30%, 20%, 10% -- i.e., this is a linear "tail", rather than a Zipf's Law tail.
Is there such an algorithm which approximates a Zipf's Law distribution?
What about other power laws/long-tail distributions -- e.g., i^(-2) ? Other common distributions?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun