Harnessing the power of two crossmatches

Avrim Blum; Anupam Gupta; Ariel D. Procaccia; Ankit Sharma

doi:10.1145/2492002.2482569

Harnessing the power of two crossmatches

Avrim Blum, Anupam Gupta, Ariel D. Procaccia, Ankit Sharma

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. However, if two crossmatches could be performed per patient, in principle significantly more successful exchanges could take place. In this paper, we ask: If we were allowed to perform two crossmatches per patient, could we harness this additional power optimally and efficiently? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal | up to lower order terms | solutions on random large kidney exchange instances.

Original language	English (US)
Title of host publication	EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
Publisher	Association for Computing Machinery
Pages	123-140
Number of pages	18
ISBN (Print)	9781450319621
DOIs	https://doi.org/10.1145/2492002.2482569
State	Published - 2013
Event	14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States Duration: Jun 16 2013 → Jun 20 2013

Publication series

Name	Proceedings of the ACM Conference on Electronic Commerce

Other

Other	14th ACM Conference on Electronic Commerce, EC 2013
Country/Territory	United States
City	Philadelphia, PA
Period	6/16/13 → 6/20/13

Keywords

Kidney exchange
Random graphs

ASJC Scopus subject areas

Software
Computer Networks and Communications
Computer Science Applications

Access to Document

10.1145/2492002.2482569

Cite this

Harnessing the power of two crossmatches. / Blum, Avrim; Gupta, Anupam; Procaccia, Ariel D. et al.
EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce. Association for Computing Machinery, 2013. p. 123-140 (Proceedings of the ACM Conference on Electronic Commerce).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Blum, A, Gupta, A, Procaccia, AD & Sharma, A 2013, Harnessing the power of two crossmatches. in EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce. Proceedings of the ACM Conference on Electronic Commerce, Association for Computing Machinery, pp. 123-140, 14th ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, United States, 6/16/13. https://doi.org/10.1145/2492002.2482569

@inproceedings{76217f532d9e4070abb357842406ac25,

title = "Harnessing the power of two crossmatches",

abstract = "Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. However, if two crossmatches could be performed per patient, in principle significantly more successful exchanges could take place. In this paper, we ask: If we were allowed to perform two crossmatches per patient, could we harness this additional power optimally and efficiently? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal | up to lower order terms | solutions on random large kidney exchange instances.",

keywords = "Kidney exchange, Random graphs",

author = "Avrim Blum and Anupam Gupta and Procaccia, {Ariel D.} and Ankit Sharma",

year = "2013",

doi = "10.1145/2492002.2482569",

language = "English (US)",

isbn = "9781450319621",

series = "Proceedings of the ACM Conference on Electronic Commerce",

publisher = "Association for Computing Machinery",

pages = "123--140",

booktitle = "EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce",

note = "14th ACM Conference on Electronic Commerce, EC 2013 ; Conference date: 16-06-2013 Through 20-06-2013",

}

TY - GEN

T1 - Harnessing the power of two crossmatches

AU - Blum, Avrim

AU - Gupta, Anupam

AU - Procaccia, Ariel D.

AU - Sharma, Ankit

PY - 2013

Y1 - 2013

N2 - Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. However, if two crossmatches could be performed per patient, in principle significantly more successful exchanges could take place. In this paper, we ask: If we were allowed to perform two crossmatches per patient, could we harness this additional power optimally and efficiently? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal | up to lower order terms | solutions on random large kidney exchange instances.

AB - Kidney exchanges allow incompatible donor-patient pairs to swap kidneys, but each donation must pass three tests: blood, tissue, and crossmatch. In practice a matching is computed based on the first two tests, and then a single crossmatch test is performed for each matched patient. However, if two crossmatches could be performed per patient, in principle significantly more successful exchanges could take place. In this paper, we ask: If we were allowed to perform two crossmatches per patient, could we harness this additional power optimally and efficiently? Our main result is a polynomial time algorithm for this problem that almost surely computes optimal | up to lower order terms | solutions on random large kidney exchange instances.

KW - Kidney exchange

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=84879766463&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879766463&partnerID=8YFLogxK

U2 - 10.1145/2492002.2482569

DO - 10.1145/2492002.2482569

M3 - Conference contribution

AN - SCOPUS:84879766463

SN - 9781450319621

T3 - Proceedings of the ACM Conference on Electronic Commerce

SP - 123

EP - 140

BT - EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce

PB - Association for Computing Machinery

T2 - 14th ACM Conference on Electronic Commerce, EC 2013

Y2 - 16 June 2013 through 20 June 2013

ER -

Harnessing the power of two crossmatches

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this