应用数学
應用數學
응용수학
MATHEMATICA APPLICATA
2005年
3期
411-416
,共6页
装箱%在线算法%核元%性能界
裝箱%在線算法%覈元%性能界
장상%재선산법%핵원%성능계
本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NP-Hard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.
本文討論瞭一類在線變呎吋裝箱問題,假定箱子的呎吋可以是不同的.箱子是在線到達的,僅噹箱子到達後其呎吋纔知道.給定一箇帶有覈元的物品錶及其上的覈元關繫圖.我們的目標是要將錶中元素裝入到達的箱子中,保證任何箱子所裝物品不互為覈元,即所裝物品對應的點所導齣的子圖是箇空圖,併使得所用的箱子總長最小.我們證明瞭該問題是NP-Hard的,併給齣瞭基于圖的點染色、圖的糰分解和基于揹包問題的近似算法,給齣瞭算法的時間複雜度和性能界.
본문토론료일류재선변척촌장상문제,가정상자적척촌가이시불동적.상자시재선도체적,부당상자도체후기척촌재지도.급정일개대유핵원적물품표급기상적핵원관계도.아문적목표시요장표중원소장입도체적상자중,보증임하상자소장물품불호위핵원,즉소장물품대응적점소도출적자도시개공도,병사득소용적상자총장최소.아문증명료해문제시NP-Hard적,병급출료기우도적점염색、도적단분해화기우배포문제적근사산법,급출료산법적시간복잡도화성능계.
