@techreport{oai:ipsj.ixsq.nii.ac.jp:00223365,
 author = {藤原, 直紀 and 徳山, 豪},
 issue = {2},
 month = {Jan},
 note = {d 次元の n 個のベクトル列が与えられたとき，列ベクトルを並べ替えて d×n の行列として考える．行列の様子は列ベクトルの順序によるが，これを目的関数を最大/最小にするような列ベクトルの順列を見つける問題として定式化する．目的関数は，行列の各行に対するファーストフィット非減少部分列の要素の効用の和で定義することで，最大化問題をソーティング問題の自然な一般化として考えることができる．本論文では，d が定数の場合には，多項式時間アルゴリズムが構成できることを示し，d が一般である場合に対しては，集合被覆問題や劣モジュラ最適化との関係を調査し，計算複雑度を考察する．, Given a set of n vectors with d dimensions, we consider a d × n matrix arranging them as column vectors. The matrix depends on the order of the vectors, and we consider the problems of finding the optimal permutation of column vectors to maximize/minimize an objective function. Our objective function is defined by using the first-fit maximal non-decreasing subsequences of row vectors of the matrix, and the maximizing problem can be considered as a natural generalization of sorting. We consider the complexity of the problems and give polynomial time algorithms if d is a constant. We also discuss variants of the problems to relate to min-sum set covering and submodular optimization.},
 title = {魔女の最適調合問題－非減少部分列の最適化に基づく多次元ソーティング問題},
 year = {2023}
}