| ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM |
| |
| 引用本文： | Z.-Q. Luo, D.L. PARNAS(Communications Research Laboratocy Department of Electrical and Computer Engineering,Mcmaster University,Hamilton,Ontario,Canada L8S 4K1). ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM[J]. 应用数学学报(英文版), 1994, 10(4): 434-440. DOI: 10.1007/BF02016333 |
| |
| 作者姓名： | Z.-Q. Luo D.L. PARNAS(Communications Research Laboratocy Department of Electrical and Computer Engineering Mcmaster University Hamilton Ontario Canada L8S 4K1) |
| |
| 作者单位： | Communications Research Laboratocy Department of Electrical and Computer Engineering，Mcmaster University，Hamilton，Ontario，Canada L8S 4K1 |
| |
| 摘 要： | ＯＮＴＨＥＣＯＭＰＵＴＡＴＩＯＮＡＬＣＯＭＰＬＥＸＩＴＹＯＦＴＨＥＭＡＸＩＭＵＭＴＲＡＤＥＰＲＯＢＬＥＭＺ．－Ｑ．Ｌｕｏ；Ｄ．Ｌ．ＰＡＲＮＡＳ（ＣｏｍｍｕｎｉｃａｔｉｏｎｓＲｅｓｅａｒｃｈＬａｂｏｒａｔｏｃｙＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｉｃａ...
|
| 收稿时间： | 1993-03-16 |
On the computational complexity of the maximum trade problem |
| |
| Z. -Q. Luo,D. L. Parnas. On the computational complexity of the maximum trade problem[J]. Acta Mathematicae Applicatae Sinica, 1994, 10(4): 434-440. DOI: 10.1007/BF02016333 |
| |
| Authors: | Z. -Q. Luo D. L. Parnas |
| |
| Affiliation: | (1) Communications Research Laboratory Department of Electrical and Computer Engineering, Mcmaster University, L8S 4K1 Hamilton, Ontario, Canada |
| |
| Abstract: | 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 an “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. |
| |
| Keywords: | Computational complexity maximum trade problem 3-SAT problem |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
