【结构集分划】.pdf
浙江大学研究生学位论文用纸P 摘 要 一般性形下,集分划是NP一hard问题,人们研究集分 划的一大方向就是寻找能在多项成时间肉解决的子问题,最 近.S、Anily和A.Federgruen 研究了两类特殊结构.他们 下了一个问题。本文第一却分解决了这个么开问题。本文的第 S—,I51) 的陈羽束 集分划。我寻书了一些充分条件,使得最优集分划记为 {S,S*,SH具有某种连质结物,而这种性质使得我 们能在线性时间里解决拟陈约束2一分划,并给出了 类侧于贪萎法的算洁
浙江大学研究生学位论文用纸P.Contents Sunmury PartI Introaucten_ marl resut PartI Intreauctuen-Notation and de Sutficitcondition algorithm anc ConclusiEn Reforences
浙江大学研究生学位论文用纸P 第一部分结拘集分划 引言 本部分所做的工作是有关第二个方向的,在句绍本部分工 作之苔,我们必须窗单地介绍一下问题的情景以及一些必 要的空义。我们先引一生空义(参考[1].[4].[5]) E=(e,e,.,Cn)是个有限集合,每个元素C:却有一个 对在的放重生,并且正中的元素披权重成送增顺多排列,即有