-
混雑ゲームを用いた交通渋滞の定量評価と交通施策支援
-
実用的オークションシステム開発
電子商取引が実用化され，時間的、空間的制約を受ける事無くサービスを享受できるようになった．今後既存取引の電子商取引化が予想されるため，既存取引に見られるより複雑な取引を円滑に行うためのシステム開発が急務である．一方で，電子商取引は，既存研究によって複雑な取引モデルや状況の数理的解析が行われてきたが，実用化に至った研究は少ない．本研究の目的は，種々のオークションモデルにおける実用化を妨げている問題点を明らかにし，それらの問題点について経済学，情報科学，数理最適化の知識を融合させ，具体的に解決を試みる事によって，実用的なオークションシステムを開発し，新たな市場を創造することである．
-
グリッドトロイダルグラフ上の情報拡散ゲームにおけるナッシュ均衡
We consider a competitive diffusion process for two players on two-dimensional toroidal grid graphs. Pure Nash equilibria for the game are completely characterized; i.e., for arbitrary-sized toroidal grid graphs, we list all the initial positions that are pure Nash equilibria.
-
降雪地域における除雪車経路最適化
This paper proposes a heuristics method for huge task allocation problem over snowblower tasks. It is difficult to solve the huge task allocation problem. A snowblower problem includes a task allocation problem and agents scheduling problem. Given a directed graph as city map, we should consider some edge-disjoint partitions of the graph as allocation. A graph partition problem is a fundamental problem of combinatorics, there are some effective algorithms for the problem. However, in the case that we consider the task allocation and scheduling, the graph partition problem is too difficult. Because of this fact, we employ an agent simulation for solving the snowblower problem.
-
データセンター省電力化
データセンターでの消費電力低減の手法として,低負荷の仮想計算機を高速にマイグレーションし て集約し,使用していない物理計算機を省消費電力モードで運用する方法がある.これを実現するに は,消費電力を抑えつつユーザ体験の劣化を防ぐ,負荷が変動する VM 群を現実的な時間で再配置す る,再配置時のマイグレーションによる通信衝突を考慮する,という課題がある.本研究では,ユー ザ体験を劣化させることなく省電力化を図る仮想計算機パッキング問題に対するマッチングベースア ルゴリズム(MBA)を提案,評価する.提案手法では,再配置時に 1 つの計算機が送受信する VM 数を制限し,VM と計算機の組合わせをグラフのマッチングで表すことで,多項式時間で適切な再配 置プランニングを可能にする.評価では,提案手法を 0-1 整数計画法で定式化して商用ソルバを用い る手法とグリーディな手法で消費電力削減効果,計算時間,ユーザ体験の劣化について比較する.実 験から,1) 提案手法により最適な再配置を高速に決定でき,ある程度サイズの大きな問題に対しても 許容できる計算時間内に求解できる,2) 再配置により大幅な消費電力削減効果がある,3) ユーザ体 験は消費電力削減効果に反比例する傾向があることが示された.
-
ハイパーグラフ上の最大密度部分集合問題
ウェブグラフや社会ネットワークにおけるコミュニティ抽出はネットワーク分析で重要な役割を果たして いる.コミュニティは,対象となるネットワークをグラフとして表現したとき,密な部分グラフとして定義され, 様々な抽出アルゴリズムが研究されてきた.一方で,複雑なネットワークを表現するのに,いくつかのノードの集 まりや属性の違いなどを表現するハイパーグラフが注目されている.本研究ではグラフ上で隣接数を基に定義され たコミュニティをハイパーグラフ上に拡張し,4 つの拡張モデルを定義する.そして,いずれのモデルに対しても 最小カットアルゴリズムを利用した抽出アルゴリズムが構築できることを示す.また,共著者データを用いてモデ ルの違いによる抽出コミュニティの相違を検証する.