On the computational complexity of the maximum trade problem

Z. Q. Luo, D. L. Parnas

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)434-440
Number of pages7
JournalActa Mathematicae Applicatae Sinica
Volume10
Issue number4
DOIs
StatePublished - Oct 1994

Keywords

  • 3-SAT problem
  • Computational complexity
  • maximum trade problem

Fingerprint Dive into the research topics of 'On the computational complexity of the maximum trade problem'. Together they form a unique fingerprint.

Cite this