In several practical circumstances we have to solve a problem whose instance
is not a priori completely known. Situations of this kind occur in computer
systems and networks management, in financial decision making, in robotics etc.
Problems that have to be solved without a complete knowledge of the instance
are called on-line problems. The analysis of properties of on-line problems and
the design of algorithmic techniques for their solution (on-line algorithms) have
been the subject of intense study since the 70-ies, when classical algorithms for
scheduling tasks in an on-line fashion  and for handling paging in virtual
storage systems  have been first devised. In the 80-ies formal concepts for
analyzing and measuring the quality of on-line algorithms have been introduced
 and the notion of competitive analysis has been defined as the ratio between
the value of the solution that is obtained by an on-line algorithm and the value of
the best solution that can be achieved by an optimum off-line algoritm that has
full knowledge of the problem instance. Since then a very broad variety of online
problems have been addressed in the literature [14, 19]: memory allocation
and paging, bin packing, load balancing in multiprocessor systems, updating and
searching a data structure (e.g. a list), scheduling, financial investment, etc.
This book constitutes the refereed proceedings of the Third International Conference on Theory and Applications of Models of Computation, TAMC 2006, held in Beijing, China, in May 2006. The 75 revised full papers presented together with 7 plenary talks were carefully reviewed and selected from 319 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed.