重みつき集合充填問題に対する局所改善法について

摘要

重みつき集合充填問題とは，重みのついた部分集合の族が与えられたとき，互いに素な部分集合からなる族のうち重み最大のものを見つける問題である。 特に部分集合の最大サイズがkである問題をk－SetPaCkingproblem（k－SP）という。 本稿では，局所探索法の一種であるt－local searchアルゴ）ズムを利用し，部分集合の重みが1とwに制限されたた－SP（但し，w≧5／2）に対し，近似比率がk(k-1)~s-2/2(k-1)~s-2（但し，f＝2g）の近似アルゴリズムを提案する．