[ Japanese / English ]

Project Outline

Since the 90's, popular evaluation of discrete algorithms has changed dramatically, i.e., from the conventional time/space efficiency to the quality of their solutions. The main reason is new opportunities of computer usage in which exact calculation is intrinsically hard because of intractability of many important problems, insufficiency of input information in the on-line setting, and so on. In such a transition period, our objective is to investigate how to guarantee the performance of algorithms based on the "social impact" and to develop a new paradigm for the design and analysis of such algorithms. To this goal, our three major approaches are Model Research fully reflecting the social impact, Lower-Bound Research suggesting performance limits and Upper-Bound Research by developing novel algorithms.


Project Leader

Advisory Committee