NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17374

Internet Message Format | 1992-12-23 | 1.7 KB

Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!ames!agate!dog.ee.lbl.gov!hellgate.utah.edu!fcom.cc.utah.edu!swillden
From: [e-mail] (Shawn Willden)
Newsgroups: sci.math
Subject: Christmas tree visiting...
Message-ID: <[e-mail]>
Date: 23 Dec 92 19:08:55 GMT
Sender: [e-mail]
Organization: University of Utah Computer Center
Lines: 32
X-Newsreader: Tin 1.1 PL3

An interesting problem...

A few weeks ago, my grandmother invented a "Christmas tree visiting
party" that she wanted to make a new family tradition.  The idea is to
pick an evening close to Christmas in which each family within the
extended family will visit the home of each other family to see their
Christmas tree and visit for a few moments.  One obvious constraint on
scheduling is that when family X shows up to the home of family Y,
family Y must be present.

The problem then, is stated:  Given N families and a graph representing
the distances (travel times) between homes, devise a schedule of
visits that minimizes travel time and ensures
    (1) that in a single evening all families will visit all other
    families and
    (2) each family will be home when each of the others comes to
    visit.

The schedule devised by my grandmother was decidedly suboptimal
(though I'd say she did quite well) so I (the mathematician) offered
to create a better schedule for her, thinking the problem would not be
that tough.

After several hours of (enjoyable) struggle, I'm not much closer to a
real solution, though I have devised a fairly good schedule, so I
thought I'd pass this on and let some of you play with it...

Shawn

--
Shawn Willden
[e-mail]