| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-09-18 13:25 媒介変数表示される重みに対する最大後悔最小化1-センター問題 ○大勝章平・加藤直樹（関西学院大）・照山順一・東川雄哉（兵庫県立大）・巳波弘佳（関西学院大）  COMP2018-13 |
|
| 抄録 | （和） | 本稿では,ロバスト最適化の一枠組みである最大後悔最小化モデルを用いて,重み付き無向グラフにおけ る 1-センター問題を扱う.入力グラフは,各頂点の重みを時刻に対して正数を返す関数として,また各辺の長さを正 数として持つ.時刻 t において,施設配置点 x に対する頂点 v の重み付き距離を,グラフにおける x-v 間の最短距離 と v の重みの積として定義するとき,施設配置点 x の配置コストは,x に対する各頂点の最大重み付き距離として定 義される.また,時刻 t における施設配置点 x の後悔は,t における x の配置コストと最適配置コストの差として定義 される.このとき,全時刻にわたる後悔の最大値を最小化する施設配置点の発見が目的となる.本稿では,グラフが パス・木の場合に対する多項式時間アルゴリズムを提案する. |
| （英） | In this paper, based on the minimax regret model which is an approach for the robust optimization, we consider 1-center problems in weighted and undirected graphs. In an input graph, the weight of a vertex is given as a positive function in time and the length of an edge is given as a positive value. At time t, the weighted distance of v w.r.t. x is defined as the product of the shortest distance from v to x and the weight of v, and the location cost of x is defined as the maximum weighted distance w.r.t. x. The regret of x at time t is defined as the value subtracted the optimal location cost at t from the location cost of x at t. Our aim is to find the location which minimizes the maximum regret over time. We present polynomial time algorithms for the problems on paths and trees. | |
| キーワード | （和） | 最大後悔最小化 / 施設配置問題 / 多項式時間アルゴリズム / / / / / |
| （英） | minimax regret / facility location problem / polynomial time algorithm / / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 216, COMP2018-13, pp. 29-33, 2018年9月. | |
| 資料番号 | COMP2018-13 | |
| 発行日 | 2018-09-11 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-13 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2018-09-18 - 2018-09-18 |
| 開催地（和） | 九州工業大学（飯塚キャンパス） |
| 開催地（英） | Kyusyu Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-09-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 媒介変数表示される重みに対する最大後悔最小化1-センター問題 |
| サブタイトル（和） | |
| タイトル（英） | Minimax regret 1-center problems with parametric weights |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最大後悔最小化 / minimax regret |
| キーワード(2)（和/英） | 施設配置問題 / facility location problem |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / polynomial time algorithm |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 大勝 章平 / Shohei Ookatsu / オオカツ ショウヘイ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 加藤 直樹 / Naoki Katoh / カトウ ナオキ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 照山 順一 / Junichi Teruyama / テルヤマ ジュンイチ |
| 第3著者 所属（和/英） | 兵庫県立大学 (略称： 兵庫県立大) University of Hyogo (略称： Univ. of Hyogo) |
| 第4著者 氏名（和/英/ヨミ） | 東川 雄哉 / Yuya Higashikawa / ヒガシカワ ユウヤ |
| 第4著者 所属（和/英） | 兵庫県立大学 (略称： 兵庫県立大) University of Hyogo (略称： Univ. of Hyogo) |
| 第5著者 氏名（和/英/ヨミ） | 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ |
| 第5著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-09-18 13:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-13 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.216 |
| ページ範囲 | pp.29-33 |
| ページ数 | 5 |
| 発行日 | 2018-09-11 (COMP) |
[研究会発表申込システムのトップページに戻る]