给定物品组合情况下组合分配问题计算复杂性研究

摘要

本文详细研究了在最小分配单位为给定物品组合情况下的组合分配问题模型，从计算理论的角度通过构造性方法证明该问题可在多项式时间规约为于本文首先提出的无向图边带权最大独立集问题。其次给出了边带权最大独立集问题的定义并证明该问题属于NP-hard问题。同时还证明了任何无向图边带权最大独立集问题可在问题多项式时间反向规约于组合分配问题。用基于度数的子图划分方法给出边带权最大独立集问题的一个近似度为「(1+△′)/3」的近似算法，其中△′为图中点的最大度数。最后根据组合分配问题与边带权最大独立集问题可相互规约的性质给出了这两个问题的近似度下界。我们在本文中主要有以下工作：1.首先提出并证明了组合分配问题在最小分配单位为给定物品组合时，该问题可多项式时间规约为于无向图边带权最大独立集问题。2.给出无向图边带权最大独立集问题的定义，证明边带权最大独立集问题属于NP-hard问题；同时证明任何的无向图边带权最大独立集问题可在多项式时间规约为最小分配单位为给定物品组合情况下的组合分配问题。3.结合组合分配问题可多项式时间规约为边带权最大独立集问题的性质给出了一个同时适用于两问题的近似度为「(1+△′)/3」的近似算法△′为组合分配问题规约为无向图边带权最大独立集问题后图中点的最大度数。4.给出给定物品组合情况下组合分配问题的近似下界l12-εfor()ε＞0，其中l为参加分配的物品总数。以及边带权最大独立集问题的近似下界(V12)1-ε，for()ε＞0，V为图中边数。

目录

文摘

英文文摘

第一章引言

1.1相关领域背景知识

1.1.1机制设计

1.1.2组合分配问题

1.1.3算法机制设计

1.1.4 NP-hard问题

1.1.5近似算法

1.2我们的工作

第二章给定物品组合情况下组合分配问题的内在计算复杂性分析

2.1给定物品组合情况下组合分配问题可在多项式时间转化为边带权无向图最大独立集问题

2.2边带权无向图最大独立集问题的复杂性证明

第三章给定物品组合情况下组合分配问题的一个近似算法

第四章组合分配问题以及边带权最大独立集问题的不可近似性

第五章结论与展望

5.1结论

5.2进一步的工作

参考文献

攻读硕士学位期间参与的科研项目与发表的论文

致谢

论文独创性声明及论文使用授权声明