文献

J-GLOBAL ID：202202265118686066   整理番号：22A2920318

多様な組合せを求めるためのアルゴリズム論的アプローチ

著者 (1件)： 小林靖明 (北大 大学院情報科学研究院)
資料名： システム/制御/情報  (システム制御情報学会誌)
巻： 66  号： 11  ページ： 415-420  発行年： 2022年11月15日 
JST資料番号： G0902A  ISSN： 0916-1600  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ・いくつかの組合せ最適化問題に対する「多様な解」を求めるアルゴリズムの概観。
・組合せ最適化問題に対する多様性最大化問題の定義。
・詰め込み問題に基づく多様性最大化技法の概観。
・局所探索法に基づく近似多様性最大化手法についての概観。

シソーラス用語： *組合せ最適化問題 ,  近似法 ,  最大化問題 ,  近傍探索法 ,  多様性 ,  Hamming距離 ,  最短路問題 ,  マッチング ,  部分グラフ ,  目的関数 ,  アルゴリズム理論
準シソーラス用語： 近似アルゴリズム ,  局所探索法 ,  グラフマッチング ,  二部グラフ

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (25件)：

• [1] V. Akgün, E. Erkut and R. Batta: On finding dissimilar paths; Eur. J. Oper. Res., Vol. 121, No. 2, pp. 232-246 (2000)
• [2] N. Alon, R. Yuster and U. Zwick: Color-coding; J. ACM, Vol. 42, No. 4, pp. 844-856 (1995)
• [3] J. Baste, M. R. Fellows, L. Jaffke, T. Masarík, M. D. O. Oliveira, G. Philip and F. A. Rosamond: Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory; Vol. 303, p. 103644 (2022)
• [4] J. Baste, L. Jaffke, T. Masarík, G. Philip and G. Rote: FPT algorithms for diverse collections of hitting sets; Algorithms, Vol. 12, No. 12, p. 254 (2019)
• [5] K. Bérczi and T. Schwarcz: Complexity of packing common bases in matroids; Math. Program., Vol. 188, No. 1, pp. 1-18 (2021)

タイトルに関連する用語 (2件)： 組合せ ,  アルゴリズム