著者

藤原 直紀 徳山 豪

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2023-AL-191, no.2, pp.1-8, 2023-01-12

---

d 次元の n 個のベクトル列が与えられたとき,列ベクトルを並べ替えて d×n の行列として考える.行列の様子は列ベクトルの順序によるが,これを目的関数を最大/最小にするような列ベクトルの順列を見つける問題として定式化する.目的関数は,行列の各行に対するファーストフィット非減少部分列の要素の効用の和で定義することで,最大化問題をソーティング問題の自然な一般化として考えることができる.本論文では,d が定数の場合には,多項式時間アルゴリズムが構成できることを示し,d が一般である場合に対しては,集合被覆問題や劣モジュラ最適化との関係を調査し,計算複雑度を考察する.