抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (A), Fund Type: -, Overall Grant Amount: - (direct: 36400000, indirect: 10920000)
One of the main challenge in modern algorithm design is to cope with insufficient information.
In this study, we try to construct a general framework for design of approximation algorithms that can cope with insufficient information due to rapidly growing data size.
As a result, we give design and analysis of such algorithms for various problems in several fields such as graph problems, algorithmic game theory and randomized computation theory.