安藤映のページ

氏名

安藤映(あんどう えい)

職位

助教

最終学歴

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

学位

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

メールアドレス

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

居室

F604

生年月

1979年9月


研究分野

情報科学

研究テーマ

#P-困難問題に対する高速近似アルゴリズム

研究内容の概要

#P-困難と呼ばれる種類の難しい問題に対して,高速な近似アルゴリズムが得られるかどうかについて研究をしています.特に多次元の多面体の体積について研究しています.n次元の体積を計算する方法で乱数が使えると高速な近似アルゴリズムが存在することは知られていますが,乱数を使わずに近似計算ができるかどうかという点に興味があります.n次元の多面体は例えば,ハイパーキューブを一度だけ超平面で切断したものをナップサック多面体と言いますが,その体積を正確に計算する問題は#P-困難と呼ばれる難問です.この問題に対して,乱数を使わずに次元nで近似比1±εを達成するのにO(n3/ε)時間で完了するアルゴリズムを提案しました.このようなアルゴリズムはFPTAS(Fully Polynomial Time Approximation Scheme)と呼ばれていて,近似アルゴリズムの中では高速な部類と考えられています.他の多面体についてもFPTAS見つけられるか,もし存在しないとしたらどう証明するか,という点に興味があります.

キーワード

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


受賞歴


所属学会


外部資金導入実績


研究業績

論文

  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月.

リンク