期刊文献+

基于SMT的局部无嫉妒资源分配问题求解 被引量:2

LOCAL ENVY-FREENESS IN RESOURCE ALLOCATION BASED ON SMT
下载PDF
导出
摘要 公平分配问题在经济学、政治学和计算机科学等多个领域都受到了关注。针对不可分物品的局部无嫉妒资源分配问题,通过把问题转化为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.
作者 李炳坤 陈寅 Li Bingkun;Chen Yin(Department of Computer Science and Technology,South China Normal University,Guangzhou 510000,Guangdong,China)
出处 《计算机应用与软件》 北大核心 2020年第2期248-252,258,共6页 Computer Applications and Software
关键词 资源分配问题 局部无嫉妒 可满足性模理论 Resource allocation Local envy-freeness Satisfiability modulo theories
  • 相关文献

参考文献1

二级参考文献54

  • 1Nelson G, Oppen D C. Simplification by cooperating decision procedures[J]. ACM Transactions on Progrartmaing Languages and Systems, 1979, 1(2): 245-257.
  • 2Nelson G, Oppen. D C. Fast decision procedures based on congruence closure[J]. Journal of the ACM, 1980, 27(2): 356-364.
  • 3Shostak R E. An algorithm for reasoning about equality[J]. Communications of the ACM, 1978, 21 (7): 583-585.
  • 4Shostak R E. A practical decision procedure for arithmetic with function symbols[J]. Journal of the ACM, 1979, 26(2): 351-360.
  • 5Shostak R E. Deciding combinations of theories[J]. Journal oftheACM, 1984, 31(1): 1-12.
  • 6Armando A, Giunchiglia E. Embedding complex decision procedures inside an interactive theorem prover[J]. Annals of Mathematics and Artificial Intelligence, 1993, 8(3/4): 475-502.
  • 7Giunchiglia F, Sebastiani R. Building decision procedures for modal logics fi'om propositional decision procedures--the ease study of modal K[C]//LNCS 1104: Proceedings of the 13th International Conference on Automated Deduction, New Brunswick, USA, Jul 30-Aug 3, 1996. Berlin, Heidelberg: Springer, 1996: 583-597.
  • 8Armando A, Castellini C, Giunchiglia E. SAT-based proce- dures for temporal reasoning[C]//LNCS 1809: Proceedings of the 5th European Conference on Planning, Durham, UK, Sep 8-10, 1999.Berlin, Heidelberg: Springer, 2000: 97-108.
  • 9Pnueli A, Rodeh Y, Shtrichman O, et al. Deciding equality formulas by small domains instantiations[C]//LNCS 1633: Proceedings of the llth International Conference on Com- puter Aided Verification, Trento, Italy, Jul 6-10, 1999. Berlin, Heidelberg: Springer, 1999: 455-469.
  • 10Bryant R E, German S, Velev M N. Exploiting positive equality in a logic of equality with uninterpreted functions[C]//LNCS 1633: Proceedings of the l lth International Conference on Computer Aided Verification, Trento, Italy, Jul 6-10, 1999. Berlin, Heidelberg: Springer, 1999: 470-482.

共引文献11

同被引文献7

引证文献2

二级引证文献11

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部