基于SMT的局部无嫉妒资源分配问题求解  

LOCAL ENVY-FREENESS IN RESOURCE ALLOCATION BASED ON SMT

作　　者：李炳坤 陈寅 Li Bingkun;Chen Yin(Department of Computer Science and Technology,South China Normal University,Guangzhou 510000,Guangdong,China)

机构地区：[1]华南师范大学计算机科学与技术系,广东广州510000

出　　处：《计算机应用与软件》2020年第2期248-252,258,共6页Computer Applications and Software

摘　　要：公平分配问题在经济学、政治学和计算机科学等多个领域都受到了关注。针对不可分物品的局部无嫉妒资源分配问题,通过把问题转化为SMT(Satisfiability Modulo Theories)问题进行求解。实验结果表明,SMT求解这类NP难问题是可能的,有关资源分配问题的相关研究主要集中于理论上的分析和有关复杂度的证明。The problem of fair distribution has been concerned in many fields,such as economics,politics and computer science.In order to slove the local envy-freeness resource allocation problem of indivisible goods,this paper transforms it into SMT problem.The experimental results show that it is possible for SMT to solve this kind of NP hard.problems,and the research on resource allocation mainly focuses on theoretical analysis and the proof of complexity.

关 键 词：资源分配问题 局部无嫉妒 可满足性模理论 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]