Sunday, January 30, 2011

The Diogenes Problem

Shiva Subramanian's post yesterday about "The honest politician and other rare events", his contribution to the January INFORMS blog challenge, got me thinking about the following OR problem.  Suppose that, in Philip José Farmer's Riverworld (of recent TV movie fame), we are able to take all the politicians that ever were (excluding those still living) and pack them into a finite rectangular enclosure.  Suppose further that we are able to assign a probability to each of them being honest (and that the probability function is not identically zero, which may be the hardest assumption to swallow in this Gedankenexperiment).  Now let's say we are able to map out a path for Diogenes that minimizes the expected time until his first encounter with an honest person (I'm assuming both male and female politicians are present) in the room.  Would that path be a space-filling curve?

No comments:

Post a Comment

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.