05916941

a

05916941 Asano, Tetsuo Designing algorithms with limited work space. Ogihara, Mitsunori (ed.) et al., Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23--25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). Lecture Notes in Computer Science 6648, 1 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-20877-5_1

Summary: Recent progress in computer systems has provided programmers with virtually unlimited amount of work storage for their programs. This leads to space-inefficient programs that use too much storage and become too slow if sufficiently large memory is not available. Thus, I believe that space-efficient algorithms or memory-constrained algorithms deserve more attention. Constant-work-space algorithms have been extensively studied under a different name, log-space algorithms. Input data are given on a read-only array of $n$ elements, each having $O(\log n)$ bits, and work space is limited to $O(\log n)$ bits, in other words, a constant number of pointers and counters, each of $O(\log n)$ bits. This memory constraint in the log-space algorithms may be too severe for practical applications. For problems related to an image with $n$ pixels, for example, it is quite reasonable to use $O$(\"O$n$) work space, which amounts to a constant number of rows and columns. I will start my talk with a simple algorithm for detecting a cycle in a graph using only some constant amount of work space (more exactly, $O(\log n)$ bits in total) and then its applications. Then, I will introduce some paradigms for designing such memory-constrained algorithms and their applications to interesting problems including those in computational geometry and computer vision.