Minimum-Entropy Coupling問題に対する貪欲アルゴリズム

摘要

Minimum-Entropy Coupling問題は，与えられた周辺分布の条件下において最小のエントロピーを達成する同時分布を求める問題である．同問題はNP-hardであり，近似解を求めるいくつかのアルゴリズムが提案されている．同問題に対して周辺分布が2つの場合にSITA2022で発表した貪欲アルゴリズムの拡張として周辺分布が3つ以上の場合の貪欲アルゴリズムを提案する．計算機実験により，与えられた周辺分布の条件下で既知のアルゴリズムと提案するアルゴリズムで導かれる同時エントロピーの値と比較する．その結果，提案するアルゴリズムは平均して同時エントロピーがより小さい同時分布を生成できる．