Harnessing the power of two crossmatches

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationEC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
PublisherAssociation for Computing Machinery
Number of pages18
ISBN (Print)9781450319621
StatePublished - 2013
Event14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States
Duration: Jun 16 2013Jun 20 2013

Publication series

NameProceedings of the ACM Conference on Electronic Commerce


Other14th ACM Conference on Electronic Commerce, EC 2013
Country/TerritoryUnited States
CityPhiladelphia, PA


  • Kidney exchange
  • Random graphs

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computer Science Applications


Dive into the research topics of 'Harnessing the power of two crossmatches'. Together they form a unique fingerprint.

Cite this