On combinatorial optimization problems on matroids with uncertain weights

Adam Kasperski and Pawel Zielinski
European Journal of Operational Research
Volume 177, Issue 2 , 1 March 2007, Pages 851-864
http://dx.doi.org/10.1016/j.ejor.2005.12.033

マトロイドの最小重み基を求める問題を考えるが，要素の重みがある閉区間に属することしか分かっていない．
いわゆる，ある種のロバスト最適化の設定．
この場合にpossibility theoryの観点から「possibly optimal base」や「necessarily optimal base」を求める問題を考える．
そして実際これらの問題を効率よく解くアルゴリズムが示されている．