安藤映のページ

氏名

安藤映(あんどう えい)

職位

助教

最終学歴

2009年九州大学大学院システム情報科学府情報工学専攻博士後期課程修了

学位

博士(工学)(九州大学)

メールアドレス

ando-ei (atmark) cis (dot) sojo-u (dot) ac (dot) jp

居室

F604

生年月

1979年9月


研究分野

情報科学

研究テーマ

不確定情報を含むネットワークの性能見積もりアルゴリズム

研究内容の概要

不確定な情報しか与えられない中で組み合わせ的な問題を解く方法を研究してい ます.様々な場面に応用があり,LSIの信号遅延・計算機ネットワーク上の情報が伝播する時間・道路網上を移動する時間の解析などが当てはまります.道路 上の移動を例 に説明すると,ある地点から別の地点へ移動するのにかかる最短時間を求める問 題を解こうとする場合,道路を移動するのにかかる時間が既知と仮定することが しばしばあります.しかし,現実問題として道路を移動するのにかかる時間は 走ってみなければ分かりません.そこでこの不確定部分を確率変数として扱います.私の研究では,この場合の最短移動時間がどんなものかを効率的に計算する 方法を探しています.

最近の研究として,上述の研究を進める上で掴んだ技術の一部は#P-困難と呼ばれる難問に対して,高速に近似解を計算する方法に応用できる事がわかってきました.

キーワード

計算量の理論、確率変数の重み付け、グラフ最適化問題、近似アルゴリズム


受賞歴


所属学会


外部資金導入実績


研究業績

論文

  1. An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, E. Ando, WALCOM2017, LNCS 10167, pp 421--432, 2017.
  2. An FPTAS for The Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution, E. Ando, S. Kijima, Algorithmica, Volume 76, Issue 4, pp 1245--1263, 2016, DOI:10.1007/s00453-015-0096-5
  3. An FPTAS for the Volume of a V-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes, Ei Ando, Shuji Kijima, arXiv:1607.06173 [cs.CC]
  4. An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral, E. Ando and S. Kijima, Proc. of ISAAC 2014, LNCS 8889, pp. 376-386, December 15-17, 2014 Jeonju, Korea.
  5. #P-hardness of Computing High Order Derivative and Its Logarithm, E. Ando, IEICE Transactions 97-A(6), pp. 1382-1384, June, 2014.
  6. Selecting Good a Priori Sequences for Vehicle Routing Problem with Stochastic Demand, E. Ando, B. Bhattacharya, Yuzhuang Hu, T. Kameda and Qiaosheng Shi, Proc. of the 8th international conference on Theoretical aspects of computing (ICTAC 2011), LNCS, 6916, pp.45-61, Springer, August 31-September 2, 2011, Johannesburg, South Africa.
  7. The Space Complexity of Leader Election in Anonymous Networks, E. Ando, H. Ono, K. Sadakane and M. Yamashita, International Journal of Foundations of Computer Science, Vol. 21, No.3, pp. 427-440, June, 2010.
  8. Approximating the longest path length of a stochastic DAG by a normal distribution in linear time, E. Ando, T. Nakata and M. Yamashita, Journal of Discrete Algorithms, Vol. 7, Issue 4, pp. 420-438, December 2009.
  9. A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems, E. Ando, H. Ono and M. Yamashita, Proc. of the 5th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA 2009), LNCS, 5792, pp. 89-103, Springer, October 26 - 28, 2009, Sapporo, Japan.
  10. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG, E. Ando, H. Ono, K. Sadakane and M. Yamashita, Proc. of the 6th conference on Theory and Application of the Models of Computation, LNCS, 5532, pp. 98-107, Springer, May 18-22, 2009, Changsha, China.

国際会議等

  1. An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, E. Ando, WALCOM2017, LNCS 10167, pp 421--432, March 29--31, 2017, Hsinchu, Taiwan R.O.C.
  2. Logging with Maximum Length Constraint, E. Ando, A. Kawamura, M. Kiyomi, E. Miyano and H. Ono, The 19th Japan-Korea Joint Workshop on Algorithms and Computation, August 30-31, 2016, Hakodate, Japan.
  3. An FPTAS for the Volume Computation of Multiply Constrained 0-1 Knapsack Polytopes Based on Approximate Convolution, E. Ando and S. Kijima, The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, June 2-5, 2015, Fukuoka, Japan.
  4. An FPTAS for the Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral, E. Ando and S. Kijima, Proc. of ISAAC 2014, LNCS 8889, pp. 376-386, December 15-17, 2014, Jeonju, Korea.
  5. Approximating the Minimum Spanning Tree Weight Distribution Function in Treewidth k Graph Using Taylor Polynomials, E. Ando, Proc. of AAAC2013, pp.12, April 19-21, 2013, Matsushima, Japan.
  6. Selecting Good a Priori Sequences for Vehicle Routing Problem with Stochastic Demand, E. Ando, B. Bhattacharya, Yuzhuang Hu, T. Kameda and Qiaosheng Shi, Proc. of the 8th international conference on Theoretical aspects of computing (ICTAC 2011), LNCS, 6916, pp.45-61, Springer, August 31-September 2, 2011, Johannesburg, South Africa.
  7. Computing the Broadcast Time Distribution Function in Networks with Stochastic Transmission Time, E. Ando and J. Peters, Proc. of The Second AAAC Annual Meeting AAAC11, pp. 52, April 16-17, 2011, Hsinchu, Taiwan R.O.C.
  8. A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems, E. Ando, H. Ono and M. Yamashita, Proc. of the 5th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA 2009), LNCS, 5792, pp. 89-103, Springer, October 26 - 28, 2009, Sapporo, Japan.
  9. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG, E. Ando, H. Ono, K. Sadakane and M. Yamashita, Proc. of the 6th conference on Theory and Application of the Models of Computation, LNCS, 5532, pp. 98-107, Springer, May 18-22, 2009, Changsha, China.
  10. An Exact Algorithm for the Stochastic Longest Path Problem in a DAG, E. Ando, H. Ono, K. Sadakane and M. Yamashita, Proc. of The Second AAAC Annual Meeting AAAC09, pp. 16, April 11-12, 2009, Hangzhou, China.
  11. A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs, E. Ando, H. Ono, K. Sadakane and M. Yamashita, 第7回情報科学技術フォーラム, pp. 7-8, September 2-4, 2008, Fujisawa, Japan.
  12. On the Distribution of the Longest Path Length in a Directed Acyclic Graph with Exponentially Distributed Edge Weights, E. Ando, H. Ono, K. Sadakane and M. Yamashita, Proc. of The First AAAC Annual Meeting AAAC08, pp. 51, April 26-27, 2008, Pokfulam, Hong Kong.
  13. The Space Complexity of the Leader Election in Anonymous Networks, E. Ando, H. Ono, K. Sadakane and M. Yamashita, Proc. of 10th Workshop on Advances in Parallel and Distributed Computational Models, pp. 1-8. April 14, 2008, Miami, Florida, USA.
  14. The Statistical Longest Path Problem and Its Application to Delay Analysis of Logical Circuits, E. Ando, M. Yamashita, T. Nakata, Y. Matsunaga, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems 2002 (TAU2002), pp.134-139, December 2-3, 2002, Monterey, California, USA.

その他学会・研究会発表

  1. 幾何双対ナップサック多面体の体積のためのFPTAS, 安藤 映, 来嶋 秀治,アルゴリズム研究会, 2016年3月.
  2. 幾何双対ナップサック多面体の体積に対するFPTAS, 安藤 映, 情報系WinterFesta, 2015年12月.
  3. 負パラメータを含む制約つきナップサック多面体の体積に関する考察, 安藤 映, 来嶋 秀治, アルゴリズム研究会, 2015年9月.
  4. ナップサック多面体の体積に対するFPTASとその拡張について, 安藤 映, OR学会九州支部, 2015年7月.
  5. 複数制約式をもつ0-1ナップサック多面体の体積に対するFPTAS, 安藤 映, 来嶋 秀治, アルゴリズム研究会, 2015年3月.
  6. ナップサック多面体の体積計算に対するFPTAS, 2014年度夏のLAシンポジウム,安藤 映, 来嶋 秀治, 2014年7月.
  7. 解析的な関数の高次導関数値計算の困難さについて,安藤映,2013年度夏のLAシンポジウム,pp. 9-1 -- 9-4,2013年7月.
  8. 確率的枝重みを持つグラフにおける最大全域木重みの分布について, 安藤映, 2012年度夏のLAシンポジウム, pp. 16-1 -- 16-8, 2012年7月.
  9. 指数分布に従う枝長さと小さな木幅を持つ無向グラフ上での二点間の最短路長さ分布の計算方法, E. Ando, J. Peters, コンピュテーション研究会, 2012年3月.
  10. 確率的な枝重み付き無向グラフ上の二点間最短路長さ分布の近似計算手法, E. Ando, J. Peters, アルゴリズム研究会,2012年1月.
  11. 確率的な枝長さを持つ無向グラフにおける最短路長さの分布関数計算, E. Ando, J. Peters, 2011年度夏のLAシンポジウム, pp. 18-1 -- 18-8, 2011年7月.
  12. 確率的な通信時間を持つネットワークにおけるブロードキャスト時間の計算手法, E. Ando, J. Peters, アルゴリズム研究会, 2011年3月.
  13. 確率的な通信時間を持つネットワークでのブロードキャスト時間計算, E. Ando, J. Peters, アルゴリズム研究会, 2010年9月.
  14. Computing the Exact Distribution Function of the Longest Path Length in DAGs with Exponentially Distributed Edge Lengths, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 電子情報通信学会総合大会, 2009年3月.
  15. 連続分布枝重み付DAGに対する最長路長さ分布の計算, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 2008年度冬のLAシンポジウム,pp. 32-1 -- 32-6, 2009年1月.
  16. DAGにおける確率的最長路問題の多項式時間解法設計ための試み, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 2008年度夏のLAシンポジウム, pp.23-1 -- 23-6, 2008年7月.
  17. Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 電子情報通信学会総合大会, 2008年3月.
  18. 指数分布に従う枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 2007年度冬のLAシンポジウム, pp. 35-1 -- 35-6, 2008年1月.
  19. 正規分布に従う枝重みを持つグラフにおける最小全域木コストの分布関数の近似手法, E. Ando, H. Ono, K. Sadakane, M. Yamashita, コンピュテーション研究会, 2007年9月.
  20. 確率的枝重みを持つグラフ上の最小全域木コストの近似見積り法に関する考察, E. Ando, H. Ono, K. Sadakane, M. Yamashita, 2006年度冬のLAシンポジウム, pp. 31-1 -- 31-6, 2007年1月.

リンク