mitchell@svax.cs.cornell.edu (Stephen G. Mitchell) (04/12/90)
Is there much interest/activity in developing "real-time algorithms"? I know there's a good deal of work on on-line algorithms, but very often without tight resource constraints. The kind of thing I'm thinking of is dynamic update algorithms, where a data structure of size n is modified by an input of size log n, and the update has to be completed in poly-log time. I know some algorithms of this type have been developed for computational geometry problems, but I don't know if they've found real world applications. Also, what progress has there been in developing algorithms of the "good, better, best" response type--i.e., where an immediate "kludge" solution is followed later by a more optimal solution. This sounds like a softening of the idea behind on-line algorithms. Finally, what sorts of computational problems arise in real-time systems, besides filters and DFT's? I would suspect that combinatorial problems (say, shortest paths in graphs, etc) would be useful in direct digital control systems, tracking systems, etc. I've not seen much algorithms design work generated from real-time applications, and was wondering where to look. Most of what I've seen concentrates on scheduling tasks with assumed computation requirements, not on the problem of reducing those requirements for specific problems. Thanks for your thoughts, --Steve Steve Mitchell mitchell@svax.cs.cornell.edu Comp Sci/Upson Hall \\ Cornell University \\ Ithaca, NY 14853