Our work on dynamic programming has emphasized finite state spaces and computational approaches that yield exact optimizations and analyses. There are two main application areas: adaptive (sequential) designs for random responses, and determining properties of graphs. There is also some effort on optimizing parallel implementations of dynamic programming. I've also listed a few open questions related to our work.
For an extensive collection of pointers to work on the subject throughout the world, visit the dynamic programming component of the World-Wide Web for Operations Research and Management Science (WORMS) pages. The material there is interesting, and includes a fun collection of graphics.
For papers, Paper.ps means a Postscript version of the paper, and Paper.pdf means a PDF version. Each Abstract is in HTML.
However, we are also interested in other criteria such as the probability of correctly identifying the better treatment at the end of the trial, or the number of times treatments are switched, which introduces new optimization constraints or forces us to evaluate an allocation procedure multiple times. We developed the technique of path induction to reduce the time required for such repeated evaluations. (Note that we had previously called path induction "forward induction", but that term proved confusing as it had been previously used.)
Here is a more more extensive explanation of adaptive designs. A survey paper which discusses the algorithms is:
Some additional papers in this area are:
We showed that for these families these properties could actually be computed in constant time (though still exponential in k) by showing that they have a closed form. We exploit the fact that the dynamic programming is essentially determining minimal weight paths of length n in a finite state space, and must ultimately reach a periodic solution (which can be detected). See
A recent result in this area is the ability to optimally design a clinical trial for 200 patients, where there are 3 different treatments available. Other researchers have only been able to handle a handful of patients when 3 treatments were considered, or they had to resort to suboptimal designs, because the time and space required grow as O(n6), where n is the number of patients. One of the things we will now be able to do is determine exactly how suboptimal their designs were, and we will be able to consider better tradeoffs such as statistical power versus failures. With simple changes, this program can also handle 2 treatments where there are 3 possible outcomes (instead of only 2, as we normally assume). We know of no previous work which achieves optimal solutions for this problem. With less simple changes, this program can handle some models of 2 treatments with delayed responses, i.e., you must make new allocations before all of the results of previous allocations are known. Here too we know of no previous optimal designs.
Bob Oehmke is the graduate student working on implementing this on an IBM SP2. He is also working on programs for several other aspects of adaptive designs, and more generally on the problem of producing efficient highly parallel programs for dynamic programming. Our most recent paper on this work is
For all of the variations mentioned in adaptive designs, there is a common open question:
Is the given dynamic programming algorithm the fastest way to determine the optimal answer?That is, dynamic programming finds the optimal answer, but often requires a great deal of time and space. Can the optimal answer be found more quickly? This question applies to a great many other problems as well.
Related to the work on fault tolerance of allocation systems in parallel computers, the following problem gives the limiting behavior, as the system becomes arbitrarily large, of being able to find a fault-free square submesh of 1/4 the size of the full mesh.
Suppose points are place uniformly and independently in the unit square, one at a time, until there is no point-free subsquare of edgelength 1/2, where the subsquare must have its sides parallel to the sides of the square. What is the expected number of points placed?(It is possible that the solution will not involve dynamic programming.) It is also interesting to know the solution if the original square has both pairs of opposite sides connected, creating a torus.
Here are some conjectures and open problems in the area of finding properties of families of graphs.
|
Copyright © 2005-2017 Quentin F. Stout |