給定物品組合情況下組合分配問題計算復雜性研究.pdf

1、本文詳細研究了在最小分配單位為給定物品組合情況下的組合分配問題模型，從計算理論的角度通過構造性方法證明該問題可在多項式時間規(guī)約為于本文首先提出的無向圖邊帶權最大獨立集問題。其次給出了邊帶權最大獨立集問題的定義并證明該問題屬于NP-hard問題。同時還證明了任何無向圖邊帶權最大獨立集問題可在問題多項式時間反向規(guī)約于組合分配問題。用基于度數(shù)的子圖劃分方法給出邊帶權最大獨立集問題的一個近似度為「(1+△′)/3」的近似算法，其中△′為圖中點的

2、最大度數(shù)。最后根據(jù)組合分配問題與邊帶權最大獨立集問題可相互規(guī)約的性質給出了這兩個問題的近似度下界。我們在本文中主要有以下工作：1.首先提出并證明了組合分配問題在最小分配單位為給定物品組合時，該問題可多項式時間規(guī)約為于無向圖邊帶權最大獨立集問題。2.給出無向圖邊帶權最大獨立集問題的定義，證明邊帶權最大獨立集問題屬于NP-hard問題；同時證明任何的無向圖邊帶權最大獨立集問題可在多項式時間規(guī)約為最小分配單位為給定物品組合情況下的組合分配問題