Research

My research interests are on developing theory and algorithms to solve real-world problems. In particular, I have been working on solving optimization problems on networks. Related topics include

  • Combinatorial Optimization and Graph Algorithms
  • Discrete Mathematics and Combinatorics
  • Mathematical modeling
  • Operations Research/Management Sciences
  • Theoretical Computer Science
  • Machine Learning
  • Combinatorial Matrix Theory
Below are titles of senior theses (written in Japanese).

修士論文・卒業研究タイトル Research topics of students

学生の学会発表は こちら

  • Generalized data center scheduling problem with time interval selection
  • 重み付き矩形領域内のグリッドグラフ最短路アルゴリズムの近似比改善
    Improved analysis of the shortest grid path algorithm for the weighted region problem on square tessellations
  • ライドシェアにおける敵対的分布の下でのオンラインマッチング
    Online matching under adversarial distributions in ridesharing
  • 2部ハイパーグラフ上の完全マッチングとΔ辺彩色の存在条件
    On the existence of perfect matching and Δ-edge-colouring in bipartite hypergraphs
  • 三角形グリッドグラフにおけるラベル付きマッチングの遷移可能性
    Reconfigurability of labeled matching in triangular grid graphs

  • 形式的べき級数を用いたBanzhaf指数を計算するアルゴリズム
  • ユークリッドTSPに対する動的計画法を用いた多項式時間近似スキーム
  • 格子の最短ベクトル問題に対するアルゴリズム
  • 素因数分解問題に対する数体篩法
  • 複数チーム対戦ゲームの優勝可能性判定問題の計算複雑度について
    On the computational complexity of the sports elimination problem with multi-player games
  • 多段階で広告を出すための予算配分モデルとその劣モジュラ性
    Budget allocation models for multi-stage advertising and their submodularity

  • 公平な仕事割り当て問題に対する近似アルゴリズム
  • 凸目的関数に対する確率的最適化手法の解析
  • H距離空間上の遅延ありオンラインマッチング問題に対する決定的主双対アルゴリズム
  • 2 部グラフのマッチング問題に対するアルゴリズムとその実験的考察
  • ストリーミングデータに対する頻出アイテムを求める省領域乱択アルゴリズム
    Space-efficient randomized algorithms for finding frequent items in the data streams

  • 単位距離グラフの性質と直積との関係
  • 検索広告割り当て問題に対する最適なオンラインアルゴリズム
  • 学校時間割問題に対するグラフの辺彩色を用いた定式化と実験的考察
  • 瓢箪パズルに対するアルゴリズムと計算困難性
  • ページランクの性質と計算方法
  • 最小費用流問題に対する組合せ的アルゴリズム
  • 変分不等式問題とその資産均衡問題への応用
  • オンライン意思決定における乗算型重み更新法
  • オンライン二部マッチング問題に対するアルゴリズムの解析
  • サービス品質を考慮した仮想サーバー配置問題に対する列生成法
  • サイズ制約付きオンラインポートフォリオ選択問題に対するアルゴリズム
  • 個別指導塾のスケジューリング問題に対する計算複雑度の解析
  • 順伝播型ニューラルネットワークの学習における最適化手法
  • 最悪時計算量解析と安定なインスタンスに対する計算量解析
  • 組合せバンディット問題に対するアルゴリズムとその応用
  • インターネット広告における複数の予算制約付き利益最大化問題に対する近似アルゴリズム

Copyright © Naonori KAKIMURA