Hiro ITO (伊藤 大雄)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3300000, indirect: 990000)
本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２１年度の主な成果は以下の通りである。 (I) 漸進型アルゴリズム(progressive algorithm)の結果をまとめた論文が論文誌に採録・出版された。「漸進型アルゴリズム」とは、データを徐々に読み込みながら段々と精度の高い解を求めていく手法であり、研究代表者によって提案されたものである。我々はこれまでに、「定数時間アルゴリズム」と「全てのデータを読み込む線形以上の計算時間のアルゴリズム」の両者が存在する任意の問題に対し、オーダの意味での各々の計算時間を悪化させることなく、両者を円滑に繋げる漸進型アルゴリズムが構築できることを証明した。これは片側誤り、両側誤りどちらにも適用可能であり、また本技法はグラフに限らず、どのような対象、モデルに対しても適用可能であると考えられ、非常に一般性のある結果である。(II) 機器をスリープ状態にしておくことで再起動の際の時間やエネルギー消費量の節減を図る制御は広く行われている。しかしスリープ状態は少しだが電力を消費し続けるので、長く保つと逆に損になる。この問題はオンライン問題の一種の「スキーレンタル問題」という形で定式化され、その競合比（小さいほど良く、１が最適）は２でこれ以上改善出来ないことが既存研究によって証明され、それが常識とされてきた。しかしその競合比２を与えるアルゴリズムは、最悪に備える為に多くの場合で明らかに無駄と考えられる動作をせざるを得なかった。そこで担当者は、競合比を2+ε（∀ε>0）と僅かに緩和することで、多くの実用的な場合にほぼ無駄が無い様に制御する方法を考案した。その結果を論文誌に投稿し採録・出版された。

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 基盤研究(C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: 1050000)
最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した．
続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした．
以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した．
このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た．
極大クリーク全列挙問題についてもさらに理論的，実験的に検討を続け，有効な進展結果を得た．

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Challenging Exploratory Research, Fund Type: -, Overall Grant Amount: - (direct: 2800000, indirect: 840000)
The object of this project is establishing fundamental techniques for the “Sublinear-Time Paradigm.” The most remarkable result in this project is presenting a universal algorithm to complex networks, e.g., web graphs and social networks. That is, we define a class of (infinite) multigraphs, named HSF (Hierarchical Scale Free), which models a kind of hierarchical complex networks and prove that every property is constant-time testable for HSF. This is the first nontrivial universal constant-time algorithm on a graph class of sparse and degree-unbounded graphs, what is called the general graphs.

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.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
We have developed much faster algorithms for finding a maximum clique. These have been accomplished by introducing a near-maximum clique finding algorithm and by applying appropriately sorting and coloring vertices to the underlying branch-and-bound algorithm for finding a maximum clique. The effectiveness of the above algorithms has been confirmed by extensive computational experiments. In addition, we have also given a weaker condition under that the maximum clique problem can be solved in polynomial time in theory.
Our previous algorithm for enumerating maximal cliques has been extended to have algorithms for enumerating maximal pseudo-cliques. They are confirmed to work effectively for the analysis of networks.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Fund Type: -, Overall Grant Amount: - (direct: 47800000, indirect: 14340000)
We make progress in the study on limits of computation by exploiting and developing state of the art techniques in discrete mathematics such as information and coding theory. More concretely, we obtain the following results: (1) resolution of various analogous problems to the P vs. NP problem, including a characterization of constant time testability of properties in sub-linear time computation and separations of Boolean circuit classes, (2) fine-grained complexity analysis of fundamental computational problems concerning graphs and constraint satisfaction problems, including a world record polynomial time approximation algorithm for the 3 coloring problem, and (3) Applications of sub-linear time computation and graph algorithms to the areas such as machine learning and big data processing, based on the results of (1)(2).

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Challenging Exploratory Research, Fund Type: -, Overall Grant Amount: - (direct: 2900000, indirect: 870000)
We considered new frameworks on algorithms mainly on puzzles and games, and have obtained the following results: (I) For the cake-cutting problem, we presented a framework on sublinear-time algorithms and gave some algorithms in the framework. (II) For the generalized shogi problem, we presented a constant-time algorithm, i.e., we showed that it is constant-time solvable. (III) For river crossing problems, we presented a new formulation that requires prohibited states for inputs and gave a polynomial-time algorithms by using expanders. (IV) For generalized shogi with n signs, we considered jankens in which draws between different signs are allowed, and found some properties, e.g., tight upper and lower bounds of the number of draws.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2500000, indirect: 750000)
This research is concerned with Game Informatics. The themes are (1) computer search of And-Or trees, and (2) computational complexity of games and puzzles.
Search of And-Or tree (game-tree) by computers generally use evaluation function. We define our game-tree model, and compare numbers of configurations to be searched by depth-first search at the designated depth of our game-tree under various evaluation functions. Our result shows that the number of configurations when an evaluation function is applied, which is as close as the perfect evaluation function with probability p (0We obtained computational complexities of some games and puzzles, and the results have been published as papers, or presented in international conferences.

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: 38300000, indirect: 11490000)
One of the main challenge in modern algorithm design is to copewith insufficient information. In this study, we try to construct a general framework fordesign and evaluation of algorithms that can cope with insufficient spatial information. Asa result, we give design and analysis of such algorithms for various problems in severalfields such as graph problems, algorithmic game theory and randomized computationtheory.