期刊文献+

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM
原文传递
导出
摘要 Consider a computer assisted trading system in which the needs and the products of the traders are compared by a computer system and the trading proceeds without attaching a dollar price to each commodity. In such a system the computer serves as aii 'intelligent' communication link between traders, enhancing the ability of producers and consumers to exchange goods. In this paper, we examine one computational aspect of such computerized trading schemes:Given a list of trading proposals (each proposal specifying the quantities of the commodities to be traded),how should one arrange the trades so that the maximum number of trades can be made in the market? We show that this maximum trade problem is computationally hard; it is NP-complete (Nondeterministic Polynomial Time Complete). We then describe some related open questions and potential solutions. Consider a computer assisted trading system in which the needs and the products of the traders are compared by a computer system and the trading proceeds without attaching a dollar price to each commodity. In such a system the computer serves as aii 'intelligent' communication link between traders, enhancing the ability of producers and consumers to exchange goods. In this paper, we examine one computational aspect of such computerized trading schemes:Given a list of trading proposals (each proposal specifying the quantities of the commodities to be traded),how should one arrange the trades so that the maximum number of trades can be made in the market? We show that this maximum trade problem is computationally hard; it is NP-complete (Nondeterministic Polynomial Time Complete). We then describe some related open questions and potential solutions.
出处 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 1994年第4期434-440,共7页 应用数学学报(英文版)
关键词 Computational complexity maximum trade problem 3-SAT problem Computational complexity maximum trade problem 3-SAT problem
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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