Approximation and computation of arbitrage in frictional foreign exchange market

Mao-Cheng Cai; Xiaotie Deng

doi:10.1016/S1571-0661(04)81019-3

Approximation and computation of arbitrage in frictional foreign exchange market

Mao-Cheng Cai
, Xiaotie Deng

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

4 Citations (Scopus)

Abstract

In this paper we study the computational complexity of arbitrage in a frictional foreign exchange market with bid-ask spreads, bound and integrality constraints. We show that the problem of detecting the existence of arbitrage is NP-complete in the general case and, moreover, for some fixed ε > 0, approximating the optimal version of the problem within a factor of n^εis NP-hard where n is the number of foreign currencies. On the other hand, we show that the optimal problem can be solved in polynomial time for two special cases of the constant number of currencies or a star-shaped exchange graph.

Original language	English
Pages (from-to)	293-302
Journal	Electronic Notes in Theoretical Computer Science
Volume	78
DOIs	https://doi.org/10.1016/S1571-0661(04)81019-3
Publication status	Published - 1 Apr 2003
Event	CATS'03, Computing: The Australasian Theory Symposium - Adelaide, Australia Duration: 4 Feb 2003 → 7 Feb 2003

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

Research partially supported by the National Natural Science Foundation of China (No.19971001, No.10171054). Research supported in part by a research grant (Project No: CityU 1081/02E) of Hogn Kong RGC, and a research grant of City University of Hong Kong.

RGC Funding Information

RGC-funded

Access Output

10.1016/S1571-0661(04)81019-3

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{27d32ebd783743139337cb31aa74fc17,

title = "Approximation and computation of arbitrage in frictional foreign exchange market",

abstract = "In this paper we study the computational complexity of arbitrage in a frictional foreign exchange market with bid-ask spreads, bound and integrality constraints. We show that the problem of detecting the existence of arbitrage is NP-complete in the general case and, moreover, for some fixed ε > 0, approximating the optimal version of the problem within a factor of nεis NP-hard where n is the number of foreign currencies. On the other hand, we show that the optimal problem can be solved in polynomial time for two special cases of the constant number of currencies or a star-shaped exchange graph.",

author = "Mao-Cheng Cai and Xiaotie Deng",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; CATS'03, Computing: The Australasian Theory Symposium ; Conference date: 04-02-2003 Through 07-02-2003",

year = "2003",

month = apr,

day = "1",

doi = "10.1016/S1571-0661(04)81019-3",

language = "English",

volume = "78",

pages = "293--302",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Approximation and computation of arbitrage in frictional foreign exchange market

AU - Cai, Mao-Cheng

AU - Deng, Xiaotie

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2003/4/1

Y1 - 2003/4/1

N2 - In this paper we study the computational complexity of arbitrage in a frictional foreign exchange market with bid-ask spreads, bound and integrality constraints. We show that the problem of detecting the existence of arbitrage is NP-complete in the general case and, moreover, for some fixed ε > 0, approximating the optimal version of the problem within a factor of nεis NP-hard where n is the number of foreign currencies. On the other hand, we show that the optimal problem can be solved in polynomial time for two special cases of the constant number of currencies or a star-shaped exchange graph.

AB - In this paper we study the computational complexity of arbitrage in a frictional foreign exchange market with bid-ask spreads, bound and integrality constraints. We show that the problem of detecting the existence of arbitrage is NP-complete in the general case and, moreover, for some fixed ε > 0, approximating the optimal version of the problem within a factor of nεis NP-hard where n is the number of foreign currencies. On the other hand, we show that the optimal problem can be solved in polynomial time for two special cases of the constant number of currencies or a star-shaped exchange graph.

UR - https://www.scopus.com/pages/publications/84988306314

UR - https://www.scopus.com/pages/publications/84988306314#tab=impact

U2 - 10.1016/S1571-0661(04)81019-3

DO - 10.1016/S1571-0661(04)81019-3

M3 - RGC 21 - Publication in refereed journal

SN - 1571-0661

VL - 78

SP - 293

EP - 302

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

T2 - CATS'03, Computing: The Australasian Theory Symposium

Y2 - 4 February 2003 through 7 February 2003

ER -

Approximation and computation of arbitrage in frictional foreign exchange market

Abstract

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this