Joint Penn-UDel
Colloquium on the Nature of Computing
Assigning Renters with Deposits to Landlords Using DNA Computing
David H. Wood
DNA model of matching with variable costs
(c) (Graphic by John Furno)
Suppose N renters, with their security deposits,
are to be matched with mutually compatible landlords.
One interesting aspect of this problem is that the formal complexity
(as N grows large)
varies greatly with the question you ask.
We present DNA algorithms for some of the hard problems.
A notable remarkable aspect of these algorithm is that the error-prone
operation of separation is not used.
We present an analysis of complexity of these algorithms.
If there are N renters, these algorithms use
O(N)
time steps during each of which
O(N^2)
operations are simultaneously carried out by reprogrammed laboratory robots.
We give a way to estimate ahead of time how much DNA will be required.
Since separation is never used, the algorithm can never construct any
candidate solutions that are not actual solutions.
Friday, October 17 at 4pm
in room Room 209 of the
Johnson Pavilion
near Spruce and 36th Streets on the
University of Pennsylvania campus.
Travel Directions are found at
http://www.upenn.edu/fm/map/dir.html
Question Complexity
Is there some way to match everyone? Easy (Polynomial)
If so, what is the minimum budget for rental deposits? Easy (Polynomial)
Show a few of the ways to match everyone. Easy (Polynomial)
Can everyone be matched using a prespecified budget? Hard (NP-complete)
In how many ways can everyone be matched? Very Hard (#P-complete)
Show all the ways everyone can be matched. Very Very Hard
(This is joint work with
T. H. Leete, M. D. Schwartz,
R. M. Williams,
J. S. Salem and H. Rubin.)