Re: The Student Dropping Problem
- From: newstome@xxxxxxxxxxx
- Date: Sat, 21 May 2005 09:56:30 -0500
Jerry --
I've always heard of this by the more politically correct name of the
"egg dropping" problem, and it's on lots of algorithms and math puzzle
lists. I know Bill Gasarch has talked about it, and I've seen it a
few other places as well. Don't know who would have talked about it
at STOC or FOCS though...
Jeremy Spinrad <spin@xxxxxxxxxxxxxxxxxxx> wrote:
> I am writing a survey on an under-taught algorithmic technique called balancing.
> Many years ago, I heard an entertaining talk at a FOCS or STOC problem on a
> search problem, which gave rise to an example I use when introducing the
> technique in my course (and once even got me in trouble when a student protested
> that it showed the insensitivity of professors towards students in our
> department!)
>
> In this talk, the speaker introduced the student dropping problem. You want to
> determine how high you can drop a student from an n story tower, and still have
> the student survive. If you have only one student to "work with", you must make n
> drops, floow by floor. However, given 2 students, you can drop the fisrt student
> every f(n) floors as long as the student survives, and drop the second studenty
> one floor at a time. The total number of drops is at most n/f(n) + f(n); to
> minimize this asymptocitcally you can set n/f(n) = f(n) and drop every sqrt(n)
> floors.
>
> You may notice similarity tosome other algorithms (eg Wigderson's approximate
> 3-coloring), because these are also examples of balancing.
>
> Can anyone tell me who the speaker in this talk was, and/or the search problem
> that he was really dealing with in the paper?
>
> Jerry Spinrad
--
That's News To Me!
newstome@xxxxxxxxxxx
.
- References:
- The Student Dropping Problem
- From: Jeremy Spinrad
- The Student Dropping Problem
- Prev by Date: Re: are Real Numbers evil?
- Next by Date: Re: are Real Numbers evil?
- Previous by thread: The Student Dropping Problem
- Next by thread: Re: The Student Dropping Problem
- Index(es):
Relevant Pages
|
