论文部分内容阅读
偏序的线性扩张问题是在一有限集D上给定一个偏序ρ，根据某一目标函数，求出ρ的线性扩张τ，使得目标函数最优。偏序的线性扩张问题有很多应用，如元搜索、生物学数据库、相似性搜索和分类学等。本文中提到的跳数问题(Jumpnumber problem)和撞数问题(bump number problem)就属于偏序的线性扩张问题。 本文考虑的目标函数是基于线性序的F距离，即求偏序的线性扩张τ使之与给定的线性序σ之间的F距离最小。我们构造了算法A，并证明了若输入的偏序是区间序，则其线性扩张是最优的。又证明了对特殊的一类偏序，即限制后是线性序和空偏序，其线性扩张也是最优的。另外我们还构造了算法B，并证明了算法B对某类特殊的偏序得到的算法解是2-近似的。