講演名 2017-01-26
Edge Load Factor Balancing 問題と既知のNP完全問題との関連について
春日 輝(創価大), 山田 正史(創価大), 篠宮 紀彦(創価大),
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 本稿では,ネットワークフロー最適化問題の一つとして提案してきた Edge Load factor Balancing (ELB)問題に関して,既知のNP完全問題である Directed Two-commodity Integral Flow (DTIF)問題と対比させることによって性質を分析した.ELB問題は,あるネットワークにおいて,フロー量と辺の容量から定義される負荷率を平滑化するように各フローの経路を求める問題として定式化している.また,ELB問題に制限を与えた場合について,DTIF問題からの還元可能性と,複雑性クラスについて考察する.
抄録(英) This paper analyzes the property of Edge Load factor Balancing (ELB) problem, which is one of network flow optimization problems by comparing it with a well-known NP-complete problem, Directed Two-commodity Integral Flow (DTIF) problem. The ELB problem is formulated as a problem to find a set of paths that smooth edge load factor defined as the ratio of the amount of flows to a capacity of an edge. The complexity class of the restricted ELB problem is discussed based on the reducibility to the DTIF problem.
キーワード(和) ネットワークフロー / 負荷分散 / NP 困難 / グラフ理論
キーワード(英) network flow / load balancing / NP-hard / graph theory
資料番号 CAS2016-83,ICTSSL2016-37
発行日 2017-01-19 (CAS, ICTSSL)

研究会情報
研究会 CAS / ICTSSL
開催期間 2017/1/26(から2日開催)
開催地(和) 機械振興会館
開催地(英) Kikai-Shinko-Kaikan Bldg.
テーマ(和) 学生セッション、一般
テーマ(英)
委員長氏名(和) 高橋 俊彦(新潟大) / 岡田 和則(NICT)
委員長氏名(英) Toshihiko Takahashi(Niigata Univ.) / Kazunori Okada(NICT)
副委員長氏名(和) 平木 充(ルネサス エレクトロニクス) / 田村 裕(中大) / 中野 敬介(新潟大)
副委員長氏名(英) Mitsuru Hiraki(Renesas) / Hiroshi Tamura(Chuo Univ.) / Keisuke Nakano(Niigata Univ.)
幹事氏名(和) 越田 俊介(東北大) / 山口 基(ルネサスシステムデザイン) / 川上 博(NTTドコモ) / 井ノ口 宗成(静岡大)
幹事氏名(英) Shunsuke Koshita(Tohoku Univ.) / Motoi Yamaguchi(Renesas) / Hiroshi Kawakami(NTT DoCoMo) / Munenari Inoguchi(Shizuoka Univ.)
幹事補佐氏名(和) 橘 俊宏(湘南工科大) / 中村 洋平(日立) / 佐藤 翔輔(東北大) / 和田 友孝(関西大)
幹事補佐氏名(英) Toshihiro Tachibana(Shonan Inst. of Tech.) / Yohei Nakamura(Hitachi) / Shosuke Sato(Tohoku Univ.) / Tomotaka Wada(Kansai Univ.)

講演論文情報詳細
申込み研究会 Technical Committee on Circuits and Systems / Technical Committee on Information and Communication Technologies for Safe and Secure Life
本文の言語 JPN
タイトル(和) Edge Load Factor Balancing 問題と既知のNP完全問題との関連について
サブタイトル(和)
タイトル(英) On Relevance between an Edge Load Factor Balancing Problem and the Conventional NP-complete Problems
サブタイトル(和)
キーワード(1)(和/英) ネットワークフロー / network flow
キーワード(2)(和/英) 負荷分散 / load balancing
キーワード(3)(和/英) NP 困難 / NP-hard
キーワード(4)(和/英) グラフ理論 / graph theory
第 1 著者 氏名(和/英) 春日 輝 / Hikaru Kasuga
第 1 著者 所属(和/英) 創価大学(略称:創価大)
Soka University(略称:Soka Univ.)
第 2 著者 氏名(和/英) 山田 正史 / Masashi Yamada
第 2 著者 所属(和/英) 創価大学(略称:創価大)
Soka University(略称:Soka Univ.)
第 3 著者 氏名(和/英) 篠宮 紀彦 / Norihiko Shinomiya
第 3 著者 所属(和/英) 創価大学(略称:創価大)
Soka University(略称:Soka Univ.)
発表年月日 2017-01-26
資料番号 CAS2016-83,ICTSSL2016-37
巻番号(vol) vol.116
号番号(no) CAS-421,ICTSSL-422
ページ範囲 pp.33-36(CAS), pp.33-36(ICTSSL),
ページ数 4
発行日 2017-01-19 (CAS, ICTSSL)