2025/08/16 更新

写真a

フクナガ　タクロウ
福永　拓郎
FUKUNAGA Takuro
所属
理工学部 教授
その他担当機関
理工学研究科情報工学専攻博士課程前期課程
理工学研究科電気・情報系専攻博士課程後期課程
連絡先
メールによる問い合わせは《こちら》から
ホームページ
https://sites.google.com/g.chuo-u.ac.jp/discrete-algo-lab/
外部リンク

学位

  • 博士（情報学） （ 京都大学 ）

  • 修士（情報学） （ 京都大学 ）

学歴

  • 2007年1月
     

    京都大学   情報学研究科   数理工学専攻   博士後期   修了

  • 2005年3月
     

    京都大学   情報学研究科   数理工学科   修士   修了

  • 2003年3月
     

    京都大学   工学部   情報学科   卒業

  • 1999年3月
     

    愛知県立明和高等学校   卒業

経歴

  • 2021年4月 - 現在

    中央大学   理工学部 情報工学科   教授

  • 2019年4月 - 2021年3月

    中央大学   理工学部 情報工学科   准教授

  • 2017年12月 - 2021年3月

    科学技術振興機構   さきがけ研究者 (兼任）

  • 2019年6月 - 2020年11月

    理化学研究所   革新知能統合研究センター   客員研究員

  • 2017年12月 - 2019年3月

    理化学研究所   革新知能統合研究センター   研究員

  • 2017年10月 - 2017年11月

    科学技術振興機構   さきがけ研究者 (専任）

  • 2013年2月 - 2017年9月

    国立情報学研究所   特任准教授

  • 2007年4月 - 2013年1月

    京都大学   大学院情報学研究科数理工学専攻   助教

  • 2007年2月 - 2007年3月

    京都大学   大学院情報学研究科数理工学専攻   助手

▼全件表示

所属学協会

  • 日本オペレーションズ・リサーチ学会

  • 情報処理学会

研究キーワード

  • 組合せ最適化

  • 適応的最適化

  • ネットワーク設計

  • 近似アルゴリズム

  • グラフアルゴリズム

研究分野

  • 情報通信 / 数理情報学  / 数理情報学

論文

▼全件表示

書籍等出版物

  • Combinatorial Optimization and Graph Algorithms

    Takuro Fukunaga, Ken-ichi Kawarabayashi（ 担当： 編集）

    Springer  2017年 

    　詳細を見る

    記述言語：英語  

    researchmap

MISC

  • ネットワークのデザイン 招待

    福永拓郎

    数理科学   58 ( 2 )   33 - 39   2020年2月

    　詳細を見る

    担当区分：筆頭著者   記述言語：日本語   掲載種別：記事・総説・解説・論説等（商業誌、新聞、ウェブメディア）  

    researchmap

  • スパイダ被覆アルゴリズム -ネットワーク設計の最新理論- 招待

    福永 拓郎

    電気情報通信学会誌   101 ( 3 )   280 - 283   2018年3月

    　詳細を見る

    記述言語：日本語   掲載種別：記事・総説・解説・論説等（学術雑誌）  

    researchmap

  • 通信ネットワークのモデル化と最適化 招待

    小林佑輔, 福永拓郎

    オペレーションズ・リサーチ : 経営の科学   60 ( 8 )   443 - 448   2015年8月

    　詳細を見る

    記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

    グラフ・ネットワークを扱う最適化問題は組合せ最適化の主要なトピックの一つである.本稿では,グラフ・ネットワーク最適化の通信ネットワークへの応用について述べる.通信技術は近年ますます複雑になっており,さまざまな新しいトピックが生まれている.本稿では,円板形領域損傷モデルにおける最大流最小カット問題と,仮想マシンの配置問題という二つの研究成果について解説する.

    CiNii Books

    researchmap

  • ネットワーク設計問題の最先端 招待

    福永 拓郎

    オペレーションズ・リサーチ : 経営の科学   56 ( 1 )   5 - 9   2011年1月

    　詳細を見る

    担当区分：筆頭著者   記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

    各点間に十分な連結度をもつネットワークを低コストで構築することを要求する最適化問題を,ネットワーク設計問題という.ネットワーク設計問題に関する理論研究の最近の進展の中心にあるのが,反復丸め法と呼ばれる手法である.本稿では,この反復丸め法について解説する.

    CiNii Books

    researchmap

講演・口頭発表等

  • NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

    Taisei Otsuji, Peter Fulla, Takuro Fukunaga

    30th International Computing and Combinatorics Conference (COCOON 2024)  2024年9月 

    　詳細を見る

    開催年月日： 2024年9月 　 　

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • 確率的離散最適化問題に対する適応的最適化 招待

    福永拓郎

    オペレーションズ・リサーチ学会学会中部支部シンポジウム  2022年12月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • ネットワーク設計における貪欲法 招待

    福永拓郎

    数理解析研究所共同研究「組合せ最適化セミナー」  2022年7月 

    　詳細を見る

    開催年月日： 2022年7月 　 　

    記述言語：日本語   会議種別：公開講演，セミナー，チュートリアル，講習，講義等  

    researchmap

  • 不確実性下での適応的最適化 招待

    福永拓郎

    日本オペレーションズ・リサーチ学会4部会・グループ合同研究会 ～確率モデルの新展開～  2021年10月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • 不確実性下での適応的最適化 招待

    福永拓郎

    日本オペレーションズ・リサーチ学会関西支部シンポジウム「最適化の理論と応用」  2020年11月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs 招待

    福永拓郎

    電子情報通信学会コンピュテーション研究会  2020年9月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • 確率的組合せ最適化問題に対する適応的アルゴリズム 招待

    福永 拓郎

    日本OR学会研究部会「最適化とその応用」  ( 中央大学，東京 )   2019年3月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Stochastic Submodular Maximization with Performance-Dependent Item Costs 国際会議

    Takuro Fukunaga

    Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)  ( Honolulu, Hawaii, USA )   2019年1月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • 適応的最適化による推測・変動データからの意思決定,

    福永 拓郎

    さきがけ研究者交流会  ( 東京 )   2019年1月  科学技術振興機構

    　詳細を見る

    記述言語：日本語   会議種別：ポスター発表  

    researchmap

  • Stochastic Submodular Maximization with Performance-Dependent Item Costs 国際会議

    Takuro Fukunaga

    NUS SoC – RIKEN AIP Workshop on Artificial Intelligence  ( National University of Singapore, Singapore )   2018年9月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • LP-Based Pivoting Algorithm for Higher-Order Correlation Clustering 国際会議

    Takuro Fukunaga

    24th International Computing and Combinatorics Conference  ( Qingdao, China )   2018年7月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • 適応的最適化による推測・変動データからの意思決定

    福永 拓郎

    さきがけ研究者交流会  ( 東京 )   2018年6月  科学技術振興機構

    　詳細を見る

    記述言語：日本語   会議種別：ポスター発表  

    researchmap

  • 単位円グラフ上での高連結度支配集合問題に対する主双対近似アルゴリズム

    福永 拓郎

    第16回情報科学技術フォーラム(FIT2017)  ( 2017年9月12日-14日，東京大学本郷キャンパス )   2017年9月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Recent progress on the network activation problem 招待 国際会議

    Takuro Fukunaga

    10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications  ( Budapest, Hungary, May 22-25, 2017 )   2017年5月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（招待・特別）  

    researchmap

  • ハイパーグラフ上の相関クラスタリングに対する近似アルゴリズム

    福永 拓郎

    情報処理学会第163回アルゴリズム研究会  ( 2017年5月12日-13日，長崎県建設総合会館 )   2017年5月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • 頂点被覆重み最小化シュタイナー木問題

    福永 拓郎

    日本オペレーションズ・リサーチ学会 2017年春季研究発表会  ( 2017年3月15日-17日，沖縄県市町村自治会館 )   2017年3月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Scalable algorithm for higher-order co-clustering via random sampling 国際会議

    Takuro Fukunaga

    Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)  ( Hilton San Francisco, San Francisco, California, USA, February 4-9, 2017 )   2017年2月 

    　詳細を見る

    記述言語：英語   会議種別：ポスター発表  

    researchmap

  • Computing a tree having a small vertex cover 国際会議

    Takuro Fukunaga

    10th Annual International Conference on Combinatorial Optimization and Applications (COCOA16)  ( City University of Hong Kong, Hong Kong, China, December 16-18 )   2016年12月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Network optimization on unit disk graphs 招待 国際会議

    Takuro Fukunaga

    Japanese Conference on Combinatorics and its Applications (JCCA2016), Mini-symposium on Discrete Convexity and Combinatorial Optimization  ( Kyoto University, Japan, May 21-25, 2016 )   2016年5月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（招待・特別）  

    researchmap

  • 線形計画緩和を利用した近似アルゴリズム 招待

    福永 拓郎

    第28回 回路とシステムワークショップ  ( 淡路夢舞台国際会議場，2015年8月3日-4日 )   2015年8月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation 国際会議

    Takuro Fukunaga

    9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications  ( Nishijin Plaza, Fukuoka, Japan, June 2-5, 2015 )   2015年6月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • 整数格子劣モジュラ関数の適応的最大化

    福永 拓郎

    情報処理学会第153回アルゴリズム研究会  ( 北海道札幌市定山渓ビューホテル, 2015年6月12-13日 )   2015年6月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Virtual machine placement for minimizing connection cost in data center networks 国際会議

    Takuro Fukunaga

    The International Workshop of Software-Defined Data Communications and Storage (SDDCS)  ( in conjunction with IEEE INFOCOM 2015, Hong Kong, April 27, 2015 )   2015年4月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Approximating the generalized terminal backup problem via half-integral multiflow relaxation 国際会議

    Takuro Fukunaga

    32nd Symposium on Theoretical Aspects of Computer Science (STACS)  ( Munich, Germany, March 4-7, 2015 )   2015年3月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Spider covers for prize-collecting network activation problem 国際会議

    福永 拓郎

    JST ERATO 河原林/湊プロジェクト合同ワークショップ 予餞会（よせんかい）Winter 2015, 〜アルゴリズムはおねえさんを救う、そして世界を変える〜  ( 2015年1月23-24日，日本科学未来館，東京 )   2015年1月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • スパイダー被覆によるネットワークアクティベーションアルゴリズム 招待

    福永 拓郎

    日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会 (SOTA)  ( 2014年12月13日，東京大学 )   2014年12月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • Deliver or hold: Approximation algorithms for the periodic inventory routing problem 国際会議

    Takuro Fukunaga

    17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)  ( UPC Barcelona, Barcelona, Spain, September 4-6, 2014 )   2014年9月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Covering problems in edge- and node-weighted graphs 国際会議

    Takuro Fukunaga

    14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)  ( July 2-4 2014, Copenhagen, Denmark )   2014年7月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • 賞金収集ネットワークアクティベーション問題に対する近似アルゴリズム

    福永 拓郎

    情報処理学会アルゴリズム研究会  ( 2014年3月3日-4日，中央大学 )   2014年3月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • 反復丸めアルゴリズム 招待

    福永 拓郎

    組合せ最適化セミナー  ( 京都大学数理解析研究所, 2013年7月24日-26日 )   2013年7月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • Iterative Rounding Approximation Algorithms for Degree-bounded Node-connectivity Network Design 国際会議

    Takuro Fukunaga

    Workshop on Flexible Network Design  ( July 29-August 2, 2013, Fields Institute, Toronto, Canada )   2013年7月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Recent progress on iterative rounding algorithms for degree-bounded network design 招待 国際会議

    Takuro Fukunaga

    8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications  ( June 4-7, 2013, Pannon University, Veszprem, Hungary )   2013年6月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（招待・特別）  

    researchmap

  • 次数制約付き点連結度ネットワーク設計問題に対する反復丸め近似アルゴリズム 招待

    福永 拓郎

    コンピュテーション研究会  ( 2012年12月10日, 九州大学 )   2012年12月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（招待・特別）  

    researchmap

  • Iterative rounding approximation algorithms for degree-bounded node-connectivity network design 国際会議

    Takuro Fukunaga

    53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)  ( October 20-23, 2012, Hyatt Regency, New Brunswick, New Jersey, USA )   2012年10月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

▼全件表示

受賞

  • 桜舞賞（研究奨励賞）

    2019年3月   理化学研究所   不確実な状況下で劣モジュラ関数最大化を行う適応的アルゴリズムの開発

    福永 拓郎

  • 研究賞奨励賞

    2014年8月   日本オペレーションズ・リサーチ学会  

    福永拓郎

共同研究・競争的資金等の研究課題

  • 不確実性をもつ組合せ最適化モデルに対する理論基盤の構築

    研究課題/領域番号：21H03397  2021年4月 - 2026年3月

    日本学術振興会  科学研究費助成事業  基盤研究(B)  慶應義塾大学

    垣村 尚徳, 田村 明久, 福永 拓郎, 澄田 範奈

    　 詳細を見る

    担当区分：研究分担者 

    配分額：17160000円 （ 直接経費：13200000円 、 間接経費：3960000円 ）

    researchmap

  • 新計算モデルにおけるアルゴリズム・最適化

    研究課題/領域番号：20H05965  2020年11月 - 2025年3月

    日本学術振興会  科学研究費助成事業  学術変革領域研究(A)  国立情報学研究所

    河原林 健一, 岩田 覚, 吉田 悠一, 福永 拓郎, 平原 秀一, Avis David

    　 詳細を見る

    担当区分：研究分担者 

    配分額：132470000円 （ 直接経費：101900000円 、 間接経費：30570000円 ）

    現在の情報検索技術（GoogleのPageRank）、セキュリティ技術（Appleの(Local) Differential Privacy）などのアルゴリズム革新は国家規模のビジネス創成につながり、現在のGAFAを作り上げた。ここで重要なのは、PageRankもDifferential Privacyもアルゴリズムおよび理論計算機科学、離散数学の基礎・理論研究であり、最初から応用を志向した仕事ではない点である。このような事実をMicrosoft、IBM、Google、Yahoo、Facebook、Amazonなどの巨大 IT企業は創業当初から認識しており、現在でもアルゴリズム、離散数学に手厚いサポートをしている。
    本研究では、このような背景を踏まえ、理論分野のさらなる強化、特にグラフアルゴリズム、計算量理論、組合せ最適化のそれぞれの分野での世界的な研究成果発信と学術変革を目指す。またこれらを通して研究領域内での「人材育成」および、コロナ期における世界的なアルゴリズム国際共同研究拠点構築を目指す。

    researchmap

  • 先進通信技術のための新たなネットワーク設計理論の構築

    研究課題/領域番号：21K11759  2021年4月 - 2024年3月

    日本学術振興会  科学研究費助成事業  基盤研究(C)  中央大学

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者 

    配分額：4030000円 （ 直接経費：3100000円 、 間接経費：930000円 ）

    本研究の目的は，ネットワーク設計の理論をさらに発展させ，最先端通信技術にも有用な数理技術を得ることである．例えば，最先端通信技術を支える無線通信では，無線電波を送受信するためのコストや電波の干渉，環境ノイズの影響による不確実性など，これまでのネットワーク設計の枠組みでは扱い難い特徴を持つ．また，多くの通信ネットワークは高い要求を満足させるために計画的な運用を行う必要があり，その中で，ネットワーク設計のこれまでの研究では取り上げられてこなかった課題が多く存在する．本研究ではこれらの要素や課題をネットワーク設計の枠組みの中でモデル化し，数理技術に裏打ちされた新たなアルゴリズムの開発に挑む．
    2021年度は，分散データベースにおける効率的なスケジューリングを動機として提案された共フロースケジューリング問題の研究に取り組んだ．共フロースケジューリング問題に対する時刻インデックス線形計画緩和の整数性について調べ，これまで知られていた結果を改善する新たな上界値を得ることに成功した．その過程で，共フロースケジューリング問題とハイパーグラフマッチングとの関連について新たな発見を得るなど，今後の進展も期待できる研究成果を得ることができた．
    また，並行してセンサーネットワークの分散制御に関する研究を進めるために，課題の特定など環境整備を行った．通信プロトコルに関する書籍や関連分野の論文の調査を通して，情報収集を行った．

    researchmap

  • 適応的最適化による推測・変動データからの意思決定

    2017年10月 - 2021年3月

    科学技術振興機構  さきがけ 

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    researchmap

  • 連続緩和法の高速化による高性能組合せ最適化アルゴリズムの実用化

    2017年4月 - 2020年3月

    日本学術振興会  科学研究費  基盤研究(C) 

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    配分額：4550000円 （ 直接経費：3500000円 、 間接経費：1050000円 ）

    researchmap

  • 反復丸め法に基づく近似アルゴリズムの研究

    2013年4月 - 2016年3月

    日本学術振興会  科学研究費  若手研究(B) 

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    配分額：4160000円 （ 直接経費：3200000円 、 間接経費：960000円 ）

    researchmap

  • ネットワーク構造への変換に基づくアルゴリズム設計技術

    研究課題/領域番号：23500015  2011年 - 2013年

    日本学術振興会  科学研究費助成事業  基盤研究(C)  京都大学

    永持 仁, 趙 亮, 福永 拓郎

    　 詳細を見る

    担当区分：研究分担者 

    配分額：5070000円 （ 直接経費：3900000円 、 間接経費：1170000円 ）

    主にグラフ構造を対象として離散最適化問題に対するアルゴリズムを設計する．
    最大独立点集合問題などNP-困難である幾つかの重要な問題に対して，近似アルゴリズムや厳密アルゴリズムの設計を行った．
    近似アルゴリズムについてはその近似性能を理論的に解析し，厳密アルゴリズムについては計算量の上界を理論的に解析した．とくに，厳密アルゴリズムの設計においては，シフトによる慣らし解析，カット点対に基づく分解，再帰方程式集合の最大根の導出法など新しいアルゴリズム設計技術を得ることができた．

    researchmap

  • 離散最適化問題に対する効率的なアルゴリズムの研究

    2011年9月 - 2012年8月

    京都大学教育研究振興財団  在外研究長期助成 

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    researchmap

  • 汎用的なネットワーク設計問題に対するアルゴリズムの研究

    研究課題/領域番号：20700008  2008年4月 - 2012年3月

    日本学術振興会  科研費  若手研究(B)  京都大学

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    配分額：4290000円 （ 直接経費：3300000円 、 間接経費：990000円 ）

    ネットワーク設計問題とは,安定的で効率の良いネットワークを構築したり制御したりすることをモデル化した組合せ最適化問題の一種である.本研究では,ネットワーク設計における様々な課題を汎用的な組合せ最適化問題としてモデル化し,その数理的性質の解析とアルゴリズム開発を行った.特に,連結度制約と次数制約を持つネットワーク設計問題,劣モジュラシステム分割問題,集合間連結性に関する要求を持つグラフの向き付け問題,供給点配置問題などの問題について新たな成果を得た.

    researchmap

  • 図形充填問題に対するプラットフォームモデルの構築

    研究課題/領域番号：20500012  2008年 - 2010年

    日本学術振興会  科学研究費助成事業  基盤研究(C)  京都大学

    永持 仁, 福永 拓郎

    　 詳細を見る

    担当区分：研究分担者 

    配分額：4550000円 （ 直接経費：3500000円 、 間接経費：1050000円 ）

    本研究では,2次元あるいは3次元の物体を充填するMulti-sphere Schemeを提案し,その構成要素の設計や図形や描画に関する基礎理論の研究を行った.3次元物体の三角形メッシュデータからグラフ論的な解析の下で直接,球集合近似データを構築する方法を得た.また,Multi-sphere Schemeに対する3Dインターフェイスを作成し,実験結果の可視化ができるようになった.2次元における矩形のパッキングを厳密に解くソフトウエアの性能を改良し,未解決あったベンチマーク問題を世界で初めて解くことに成功している.基礎理論の結果として,任意の3点連結の分解構造を2次元のグラフ描画を使ったデータ構造の発見や3次元の非凸多面体の作るグラフの特徴付けに関する理論的研究成果が得られた.特に後者の結果は,80年前に得られたSteinitzの定理を非凸多面体の場合へ初めて拡張することに成功した成果である

    researchmap

  • グラフの点集合間連結性に関するアルゴリズムの研究

    研究課題/領域番号：19800017  2007年10月 - 2008年3月

    日本学術振興会  科学研究費  若手研究 (スタートアップ)  京都大学

    福永 拓郎

    　 詳細を見る

    担当区分：研究代表者  資金種別：競争的資金

    配分額：2718000円 （ 直接経費：2340000円 、 間接経費：378000円 ）

    節点の重み付き次数について上限制約をもつネットワーク設計問題に対し,近似アルゴリズムの開発を行った.ここで重み付き次数とは,節点に接続する辺に与えられている重みの和のことであり,例えばグラフがある通信ネットワークを表している場合は,そのネットワーク上の各ノードに集中する負荷の大きさを表現するものである.問題はそれぞれの節点に対して重み付き次数の上限を与えたうえで,さらに必要な連結度の要求を満たすグラフの中でコスト最小のものを求める.連結度の要求が全域木であることを求めるものであるとき,我々の提案アルゴリズムは,重み付き次数上限制約を4倍違反することを許した上で,最適コストの解を計算する.また連結度要求が弱優モジュラカット関数によって与えられている場合,重み付き次数上限制約を7倍違反することを許した上で,最適コストに対して2倍の近似精度を達成する.また,これらのアルゴリズムは,コストではなく最大重み付き次数を最小化する問題や,各辺に定義された重みを両端点に分配することを許すなどのより一般的な設定を持つ問題にも適用可能である.設計手法としては,近年(重みなし)次数上限付きネットワーク設計問題への適用に関する研究が盛んなIterative Rounding法(線形計画緩和解を繰り返し丸めることによって解を求める手法)を用いている.また,Iterative Rounding法のその他の問題への適用や,線形計画アルゴリズムを利用しない組合せ的なアルゴリズムの実現の可能性について検討中である.

    researchmap

▼全件表示

委員歴

  • 2025年8月 　 　

    The 31st International Computing and Combinatorics Conference (COCOON2025)   プログラム委員  

  • 2022年9月 - 　

    Workshop on Approximation and Online Algorithms (WAOA)   プログラム委員  

  • 2016年 - 2021年

    日本オペレーションズ・リサーチ学会   Journal of the Operations Research Society of Japan, 編集委員  

  • 2016年 - 2021年

    Journal of the Operations Research Society of Japan   Associate Editor  

  • 2018年 　 　

    5th International Symposium on Combinatorial Optimization (ISCO)   プログラム委員  

  • 2018年 　 　

    5th International Symposium on Combinatorial Optimization   Program Committiee Member  

  • 2014年 - 2018年

    情報処理学会，アルゴリズム研究運営委員会   運営委員  

  • 2017年 　 　

    11th International Frontiers of Algorithmics Workshop (FAW)   プログラム委員  

  • 2017年 　 　

    11th International Frontiers of Algorithmics Workshop (FAW)   Program Committiee Member  

  • 2016年 　 　

    4th International Symposium on Combinatorial Optimization (ISCO)   プログラム委員  

  • 2016年 　 　

    27th International Symposium on Algorithms and Computation (ISAAC)   プログラム委員  

  • 2016年 　 　

    NII Shonan meeting, Current Trends in Combinatorial Optimization   Organizer  

  • 2016年 　 　

    4th International Symposium on Combinatorial Optimization (ISCO)   Program Committiee Member  

  • 2016年 　 　

    27th International Symposium on Algorithms and Computation (ISAAC)   Program Committiee Member  

  • 2016年 　 　

    NII Shonan meeting, Current Trends in Combinatorial Optimization   Organizer  

  • 2013年4月 - 2015年3月

    日本オペレーションズ・リサーチ学会研究部会OR横断若手の会   主査  

  • 2011年 　 　

    The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications   Organizing Committiee Member  

  • 2011年 　 　

    The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications   Organizing Committiee Member  

  • 2008年 　 　

    日本オペレーションズ・リサーチ学会2008年春季研究発表会   実行委員  

  • 2008年 　 　

    The 19th International Symposium on Algorithms and Computation (ISAAC)   Local Organizing Co-Chair  

  • 2008年 　 　

    The 19th International Symposium on Algorithms and Computation (ISAAC)   Local Organizing Co-Chair  

▼全件表示