演讲人： Tetsuo Asano Japan Advanced Institute of Science and Technology
时间： 2009-05-11 15:00-2009-05-11 16:00
地点：FIT Building 4-603, Tsinghua University
课件下载：点击下载
内容：

Recent progress in computer systems has provided programmers with unlimited amount of working storage for their programs.  Nowadays there are full of space-inefficient programs which use too much storage and becomes too slow if sufficiently large storage is not available.

Another requirement of limited working storage comes from applications to built-in or embedded software in highly functional hardware. Digital cameras and scanners are good examples. We measure the space efficiency of an algorithm by the number of working storage cells (or the amount of working space) used by the algorithm. Ultimate efficiency is achieved when only constant number of variables are used in addition to input array(s). Another excellent example are sensor networks; with the drops of price of flash memory even a large number of cheap sensors can be equipped with huge-volume flash drive.  While the data measured by the sensor must be stored onboard for processing, and need to be
written, it is preferable to avoid writing to the flash drive, as this is a slow and expensive operation which reduces the flash drive's lifetime. Hence we would like to use only higher level memory (e.g.\ only CPU registers) that we write into, and perform only read operations on the flash drive. We call such an algorithm "a constant-working-space algorithm."The constant-working-space algorithms should not use any working space of size depending on input size and an array storing input data is given as read-only memory so that any value in the array cannot be changed.  The same framework has been studied in the complexity theory.  A typical problem is a so-called "st-connectivity" problem: given an undirected graph $G$ of $n$ vertices in read-only memory and specified two arbitrary vertices $s$ and $t$ in $G$, determine whether they are connected or not using only constant number of variables of $O(\log n)$ bits. Reingold succeeded in proving that the problem can be solved in polynomial time.  It is a great break-through in this direction.

In this talk I will present constant-working-space algorithms for geometric problems for drawing a Voronoi diagram, Delaunay triangulation, and minimum spanning tree for a given set of points in the plane, and also one for linear programming of two variables.

个人简介:

Prof.Tetsuo Asano is now Advisor to the Presidential of JAIST (Japan Advanced Institute of Science and Technology). He got his Ph.D. from graduate school of Osaka University in 1974 under the supervision of Prof. Kokichi Tanaka. He was conference chair of ISAAC 1996 and program chair of ISAAC 2006. He was ACM Fellow in 2001 and Fellow of IPSJ (Information Processing Society of Japan) in 2005.