Saturday, March 28, 2009

The mathematics of matching kidneys

“Kidneys are unusual organs,” says the blogger and academic Michael Trick, “We are given two, though we can get by with one. So, unlike the heart, say, we each have a 'spare' that we can donate to others.” Indeed, for patients suffering from kidney failure – known more technically as end stage renal disease – one option is transplantation: taking somebody else’s healthy kidney and grafting it in the patient. In the United States, there are estimated to be more than 60,000 patients waiting for such transplants to happen. Kidneys of deceased as well as living donors can be used, and both approaches have their pros and cons. But transplants involving living donors are increasing – in the United States they are 47% of all transplants.

If a transplant involves a living donor, then who might such a donor be? Perhaps someone close to the patient – a sister, a relative, a friend. But it turns out you can’t just use any kidney. You can accept a kidney only if your blood group and the donor’s are compatible. An O recipient can accept only O kidneys; A can accept O and A; B can accept O and B; and AB can accept any kidney. And there may be other medical reasons and patient preferences too that may disallow certain transplants.

So, from the above discussion, you may end up with an incompatible donor-recipient pair, and this frequently happens in practice. But this is not a dead-end; what you can do is find another incompatible donor-recipient pair, such that the blood group of the donor in the first pair is compatible with that of the recipient in the second pair, and vice-versa. If this is the case, an exchange can happen, as shown below.

Figure 1 (Picture from here)

Both pairs are now set. Simple enough. But if you look at this from the larger, societal point of view, the problem is more nuanced. There may be thousands of such incompatible donor-recipient pairs in the waiting list. If you just go from the point of view of one pair, you are likely to find a match, but you may end up ruining options for others.

How can this happen? Well, let’s look at this simple example involving just five pairs. Each pair is represented using a node, while the edges indicate that an exchange is possible. So an exchange of the type shown in figure 1 is possible between pairs 1 and 2; 2 and 3; 2 and 4; 4 and 5. Since there is no edge between 1 and 5, the pairs cannot exchange – this might be, say, because the donor of 1 belongs to blood group B but the recipient of 5 belongs to O, ruling out an exchange.

Figure 2 (mine)

Now let’s look at possible solutions. If 2 decides to exchange with 4, then only one match is possible. Three other pairs (1, 3 and 5) will have to wait for future pairs to enter the list – until then, the recipient in each pair will be on dialysis, which is extremely expensive. But there exists a better solution: let 1 exchange with 2 and let 4 exchange with 5. Four pairs now get matches, and only one pair has to wait. Thus the latter solution maximizes the number of matches in the graph, while the former solution leaves many dissatisfied.

Imagine now that there are thousands of pairs with myriad linkages – as there indeed are in reality. Can you visually think of a graph of the type above and come up with a solution? Clearly, it’s not feasible – unless we develop the superhuman ability to delineate complex and dense graphs in our minds and traverse them. Fortunately, though, the matching of kidneys turns out to be equivalent to a well studied problem in graph theory called maximum matching. Even better, there exists an algorithm that will give a solution in quick time no matter how large your graph is. Got a thousand pairs in your list? No problem – you’ll get a solution in a few seconds! The algorithm was first proposed way back in 1965, in a groundbreaking paper by Jack Edmonds. Edmonds clearly was not into sleep-inducing technical titles that are the norm in most publications: his paper is stylishly called Paths, Trees and Flowers [1] and can be accessed easily online.

Thus did the solution to a puzzle in graph theory become relevant for a pressing medical problem of today – and it is not always possible to see such happy marriages. Not that this one is perfect: the kidney matching problem in reality is not as simple as the maximum matching problem of graph theory. Medical problems – especially transplantations – are riddled with ethical, political, logistical and cost issues. Despite this, the kidney matching problem (or the paired donation problem) is something to be celebrated. It’s a neat, easy-to-understand application, and its importance can’t be overstated.

Picture from here

The problem became known in the medical community due to a paper in the prestigious Journal of the American Medical Association (JAMA) [2]. Sommer Gentry and Dorry Segev were the principal researchers. If graph theory in an organ transplantation context seems like a unique marriage, then is it any surprise that it emerged from an actual marriage - between a mathematician and a transplant surgeon? Sommer is the mathematician; Dorry the surgeon. I met Sommer at a conference in Philadelphia last year, and chatted with her over lunch (which is how I became aware of the problem). She is currently at the US Naval Academy, while Dorry is a surgeon at John Hopkins; they live in Anapolis, near Baltimore.

But to return to the paper. There is an extensive discussion in it about the challenges that come up in kidney transplantations: national vs. regional matching, logistical issues, and how to deal with patients with greater need. The national vs. regional question is especially worth mentioning. Local and regional kidney donation programs already exist in the United States, but what if a national system was to be tried out? Clearly the availability of a larger pool of kidneys would mean more matches. But then travel and the cost of transporting organs becomes an issue. But here's the twist: the paper demonstrates that in the national system, the number of matches would increase and yet only 2.9% of the national pool would actually need to travel. Who would have guessed! But this is precisely the sort of counterintuitive insight that a mathematical model is capable of providing.

Finally, why have we discussed only 2-way exchanges so far? Indeed, we can do better. Let's consider three pairs. The donor of Pair 1 could donate to the recipient of Pair 2; the donor of Pair 2 then donates to the recipient of Pair 3; and lastly, to complete the cycle, the donor of Pair 3 donates to recipient of Pair 1. That's a 3-way exchange. Perhaps longer ones can be identified in a pool but what effect does the length of a cycle have on the number of matches in the overall pool? This is a fertile area of research, and some it has already been implemented. Recently, at the Johns Hopkins Hospital in Maryland, there was a six-way exchange – the largest of its kind – involving twelve people. And the cycle of six was completed because of an altruistic donor who was unrelated to the twelve people involved, yet gave away his/her kidney.

Indeed, if you are going to have an impact on twelve rather than two, wouldn’t you be more inclined to be altruistic?


[1] Paths, trees and Flowers, by Jack Edmonds, Canadian Journal of Mathematics (1965).

[2] Kidney paired donation and optimizing the use of live donor organs, Segev D., Gentry S., Warren D., Reeb B., and Montgomery R. Journal of the American Medical Association (2005).

Sunday, March 22, 2009

Kashmir's Buddhist past - a quick excerpt

Basharat Peer’s memoir, Curfewed Night, is about Kashmir’s woes, but there are plenty of other interesting bits in the book that have nothing to do with the dark mood of the last two decades. I love the parts where Peer writes of his visits to spiritual places – Sufi, Hindu, and Buddhist – and though some of these places are facing neglect, they are nonetheless indicative of the region’s rich and diverse religious history. For instance, it was Ashoka who founded “Srinagari (the City of Wealth) around 250 BC on the outskirts of what is modern Srinagar … it was from the seminaries of Kashmir patronised by Ashoka that missionaries spread Buddhism to China and Japan.” And here’s an excerpt about the fourth Buddhist Council that might have been held in Kashmir:
“When I was a child my father told me stories of the Fourth World Buddhist Council, which was held in Kashmir in the second century under the rule of the learned Gandharan Buddhist king Kanishka. Every now and then someone claims to have found the true location of the council but most believe it was held near the ancient Garden of Harwan on the northwestern fringe of Srinagar. On a family excursion to the garden – which is lined with waterways and shaded by towering chinar trees – my father had pointed to the hillock above and told me it was where the council was believed to have gathered. I went there a few days after visiting the Srinagar museum. A signboard, ‘Buddhist sites’, guided me to a terraced area where, in 1905, archaeologists found a stupa, prayer hall, and living quarters. In the centre of the site are remains of the stupa. I stared at its stone base and two concentric squares of roughly polished stones covered with wild grass. It was hard to imagine what it might have looked like. To the left, were four fallen stonewalls covered with moss. “That was a vihara, where the monks met,” said Mohammed Khazar, an elderly caretaker of the Archaeological Survey of India (ASI), which maintains the site. According to the Chinese traveller Hieun Tsang, more than 5000 monks had come together to debate and discuss the faith.”

Wednesday, March 18, 2009

Where the real apartheid was

Richard Dowden’s Africa: Altered States, Ordinary Miracles was one of the best books I read last year. Dowden has worked in Africa as a journalist for decades, and that experience shows in the book. I’ve already posted on the Somalia chapter, and also meant to post on other countries but got caught up with distractions. Now, however, the book is on my desk again, and looking at the marked sections, it’s clear that there are at least three of four interesting bits I’d like to convey – each bit in a separate post.

Let me begin with South Africa and the apartheid system that existed there. This is what Richard Dowden (who, by the way, is a British), experienced while traveling in that country in 1979:
At the coach station in the center of Johannesburg I got off and went to find a lavatory. It was round at the back and stank as if it had not been cleaned for months. As I came out a black man walked in. He looked startled – or was it fear? He said something angrily but I didn’t understand. Then I looked back and saw a pale patch on the wall where a notice had been taken down. This was a lavatory for blacks only. It was not the first occasion that I encountered black resentment at a white crossing the apartheid frontier.
The South African government at the time was taking some cosmetic steps that would make the country look less of an apartheid state. What kind of impact did they have? Dowden writes:
Whites and blacks had completely different experiences of what apartheid actually was. In white areas, where only a handful of the black population ever went, apartheid meant the signs saying Whites Only or Non-Whites Only. In black areas like Soweto, however, there were no Non-Whites or Whites Only signs. So while for whites for those signs were the most visible manifestation of apartheid, most blacks never even saw them. The removal of the signs – welcomed by the liberals – did not affect blacks at all.
This is a key insight, something that may not have occurred to the casual observer. The real apartheid and its debilitating effects were to be seen in black townships, places whites never visited:
Whites never went to see Soweto or Winterfeld or New Brighton. They had no conception of what life was like in these officially created slums. These places were what blacks experienced as apartheid. Systematically dispossessed of land, homes and the opportunity to work, to have a family and a future, they were a slave class whose sole purpose was to provide cheap labor for whites. Above all, apartheid stripped them of their rights as citizens and their dignity as human beings.

Saturday, March 14, 2009

China's excesses, past and present, through Yu Hua's eyes

Pankaj Mishra gives us an engrossing and elaborate portrait of the Chinese writer, Yu Hua, author of Brothers, a provocative, best-selling novel about the excesses of China’s Cultural Revolution – by any yardstick, a surreal moment in 20th century history – and the unfettered capitalist boom of the last two decades. Excerpts:
Though nearly 50, Yu, who wears his hair short and spiky, looks relatively young. He speaks in emphatic bursts, his face often flushing red, and he is quick to laugh. It was, in fact, his boisterous laugh that almost got him into trouble on the morning of the solemn announcement of Mao’s death. Responding to orders that blared out from loudspeakers, he assembled with hundreds of other students in the main hall of his small-town high school. “Funereal music was played, and then we had to hear the long list of titles that preceded Mao’s name, ‘Chairman,’ ‘Beloved Leader,’ ‘Great helmsman . . . ,’” Yu recalled. “Everyone loved Chairman Mao, of course, so when his name was finally announced, everyone burst into tears. I started crying, too, but one person crying is a sad sight; more than a thousand people crying together, the sound echoing, turns into a funny spectacle, so I began to laugh. My body shook with my effort to control my laughter while I bent over the chair in front of me. The class leader later told me, admiringly, ‘Yu Hua, you were crying so fervently!’”


Brothers strikes its characteristic tone with the very first scene, as Li Guang, a business tycoon, sits on his gold-plated toilet, dreaming of space travel even as he mourns the loss of all earthly relations. Li made his money from various entrepreneurial ventures, including hosting a beauty pageant for virgins and selling scrap metal and knockoff designer suits. A quick flashback to his small-town childhood shows him ogling the bottoms of women defecating in a public toilet. Similarly grotesque images proliferate over the next 600 pages as Yu describes, first, the extended trauma of the Cultural Revolution, during which Li and his stepbrother Song Gang witness Red Guards torturing Song Gang’s father to death, and then the moral wasteland of capitalist China, in which Song Gang is forced to surgically enlarge one of his breasts in order to sell breast-enlargement gels.


Later in the taxi home, sitting next to the driver, Yu spoke of a threat to artistic expression in China newer than state control. “I am really worried about the new nationalism,” he said. “Anything slightly critical of China appears in foreign media, and the nationalists are swarming online, attacking it. I tell these angry youth that The New York Times doesn’t criticize China as much as it criticizes America. Basically they are ignorant. They think the American media is always praising American presidents. The problem is that the younger generation hasn’t lived through poverty, collectivism; it is lacking in restraint, its references are very few, the experience is so limited...

These young nationalists have no sense of ambivalence, no idea of life’s ambiguities. But when times are hard, their attitude will change, become more mature, and because capitalism in this form cannot go on in China, it has to end, those hard times will come soon.”

Friday, March 13, 2009

A back-channel peace process

While still on Kashmir, here's a recent piece by Steve Coll that tells us of a secret peace process the Musharraf and the Manmohan Singh administrations together tried to develop -- and apparently they were making progress. Of course, with Musharraf's fall, this has been put on hold. Just to clarify, my link is not meant to be an endorsement of Musharraf or Singh. I linked because the essay, though a tad long, has a great summary of the history and broader geopolitics of the region in addition to the new angle on India-Pakistan relations. Basharat Peer of Curfewed Night is also mentioned.

(I'd forgotten to link to the essay -- my apologies to those readers who may have come here, and muttered: "Which essay is this guy talking about?")

Sunday, March 08, 2009

Kashmir in Basharat Peer's Curfewed Night


Basharat Peer was born in 1977, in Seer village in the southern corner of Anantnag district of Kashmir. His childhood, as he describes it in his book, Curfewed Night, was idyllic. To be sure, Kashmiris at the time were still opposed to Indian rule. But this dislike had not turned militant yet. In the late 1980s, though, when Basharat was in boarding school, violent struggle for an independent Kashmir pervaded every aspect of life. Young men offered themselves to fight for the cause. The Indian military, intent on crushing the movement, set up bunkers in Basharat’s boarding school. Basharat himself toyed with the idea of joining the militants before he was dissuaded by his family. Pakistan stepped up its support. Kashmiri men walked across the Line of Control (LoC), got trained, and came back to fight against Indian rule. Many men viewed this journey across the LoC as a matter of pride – a duty, a calling. As Yusuf, one of Basharat’s friends, says in Curfewed Night:
“ [Going to Pakistan] is like a certificate, a degree that you are a real militant! Otherwise people wouldn’t take you seriously.”
The Indian army brutally suppressed the separatists and set up torture chambers -- Papa II on Gupkar Road, Srinagar's own Green Zone, was the most terrifying -- in which lives were irreparably damaged. In the fight between soldiers and militants, thousands of people lost their lives. Soldiers shot down innocent protesters – the cruelest perhaps the Gawkadal Bridge Massacre – and raped women. Radical Islamic groups became stronger even as Kashmir’s Sufi traditions suffered. Those of us who are not Kashmiris know of the conflict from newspaper reports and television. But it has remained rather abstract – this blast or that blast, number of people dead, where it happened and so on. In Curfewed Night, Basharat provides a view – a deeply personal one – from the inside.

And what a disturbing view it is.

Basharat nearly lost his parents in 2001 to a mine blast, specifically meant to kill his father; one of his cousins suddenly decided to become a militant, crossed the LoC, returned, and was later killed; his Hindu Pandit friends escaped Kashmir for the safety of Jammu and other Indian cities. Basharat himself left Kashmir after finishing school. He went on to become a journalist in Delhi, and wanted badly to write about Kashmir.

Curfewed Night is a result of that yearning. From the courtyards of families who have lost their sons to the conflict, to the empty streets of Srinagar, to Sufi and Hindu shrines: Basharat carefully chronicles the embattled landscape of Kashmir in richly descriptive prose. As Chandrahas writes in his essay, Curfewed Night is “so good because it moves skillfully between close-ups of people and the long view of history, and because it describes the scars not only on the physical but also the psychological landscape of Kashmir. He treats his subjects with sensitivity and sympathy, and they respond graciously in turn.” Despite the book’s charged material – the accounts of the humiliations Indian soldiers impose on Kashmiris and the deeply personal nature of the topic – Basharat’s writing is not of the accusatory kind.


My copy of the book is full of notes – I’ve never learned so much about Kashmir, its people and what they have to go through as I have in this book. Let me give a few examples.

1. Kashmiris dread the sight of an Indian soldier. It was only on his first trip away from home that Basharat realized the fear of Indian soldiers is restricted to the state’s borders. While traveling out of Kashmir in a train,
“…two soldiers entered my compartment. Like me, the soldiers had made a twelve hour journey through the high mountains to the railway station in Jammu. Ahead of us was a fourteen hour train ride to New Delhi. The soldiers smiled and dropped their bags in the aisle. ‘Will you please make room for us?’ one of them asked a middle-aged man reading a newsmagazine. ‘We are going home after a year in Kashmir and don’t have any reservations.’ The man was unmoved. The soldier repeated his request, and as I squirmed in my seat, another passenger pointed at the floor of the dirty aisle and said, ‘You may sit there.’ I was stunned. Grandfather and I looked at each other. Unlike people in Kashmir, our north Indian fellow passengers had no reason to be scared of the soldiers: they ordered them around and the soldiers obeyed.”
2. And a return to Kashmir always means being searched, or “frisked” by soldiers – a strangely familiar routine.
We were at Banihal tunnel, which had been bored through the mountain by Swiss engineers in 1953, crossing which you see the valley of Kashmir. Two soldiers boarded the bus and began checking our luggage; the passengers walked in a queue towards a bunker serving as a security checkpost. One by one the passengers entered the checkpost, their hands raised above their shoulders. The soldiers stared at our identity cards and frisked us. There was a strange familiarity with this ritual. It was oppressive and intimate at the same time. In some perverse way, it did signal reaching home.
3. Have you ever seen lights being used in auto-rickshaws at night in India? I’ve never traveled in one with a bulb – and if there was one, I’ve never seen it used. But lights in auto-rickshaws are important in Srinagar:
“From the city centre, Lal Chowk, I boarded an auto-rickshaw. The driver switched on a bulb that cast a bright yellow light over both the driver and the passenger. You always switched on that light so soldiers could see you.”
4. Finally, an old marriage custom in Kashmir – the groom leaving for the bride’s place – was done after sunset, but this is no longer the case. Here’s why:
“Women and girls formed a circle, held hands and sang. They moved back and forth, tapped their feet on the ground, shook their heads, raised and lowered their voices. It was an old custom practiced before the groom left for the bride’s house; grooms left for the bride’s place after the sunset and returned after a late dinner. Kashmiris had discarded that centuries-old tradition the evening of May 16, 1990, when Indian paramilitaries fired upon a marriage party and raped the bride.”

Wednesday, March 04, 2009

The optimal sifting of waste

The economics of recycling is explained in this recent Economist article. India, it appears, does a great job recycling. This is because the sorting of trash, something you might have never thought about, is done extremely well. India's poor do it and they have a financial incentive -- however small that might be -- to do it well. One example from Bombay, below, of meticulous, nuanced sorting:
The swarming flies and sickly, fetid smell that fill the shed do not seem to put her off her [Mrs.Hiyale's] work. She sits on a low, pink plastic stool, behind a mound of unsorted goods which she is gradually dividing into smaller piles. Copper wiring goes in one heap, aluminium foil in another. Iron and steel is divided by thickness; the heftier pieces fetch a higher price. The same goes for plastic bags. Cloth, leather, Tetra Paks—each has its own pile. Coconut shells go into a bag hanging from the rafters.
Another woman comes in, carrying a load of plastic bottles several times her own size on her head. She will sort it by type of plastic and by colour. In another part of the shed a third woman stands knee-deep in waste paper which she is separating into cardboard, newspaper, office paper, glossy paper, coloured paper and envelopes—which, she says proudly, fetch four rupees a kilo, against just one rupee for the newspaper. [Link]
In general, "the narrower the categories into which recyclables are sorted, and the more meticulous the separation, the easier they are to process, and the higher the price they fetch." Rich countries, with their mechanized equipment designed to sift and sort, may not be as effective; machines may be more error prone and are not yet capable of recognizing nuanced categories. But rich countries can't have people in their own countries do it manually -- as happens in India -- because it is too expensive.

For more such insights, read the full piece.

Tuesday, March 03, 2009

Kumar Sangakkara on the Lahore shooting

The truth is we owe our lives to the courageous Mohammad Khalil, the driver. I will forever be grateful to him. The tyres of the bus had been shot out and he was in grave personal danger, exposed to gunfire at the front of the bus. But he was hell-bent on getting us to safety and, somehow, he got us moving again. Had Khalil not acted with such courage and presence of mind most of us would have been killed.

Standing still next to the roundabout we were sitting ducks for the 12 gunmen. We only found out afterwards that a rocket launcher just missed us as we began moving and turned for the stadium gates, the rocket blowing up an electricity pylon. Khalil saw a hand grenade tossed at us that failed to explode. Someone must have been looking over us because right now it seems a miracle we survived.


From a Pakistan perspective, it is tragic this has happened. Pakistan is a great country with a strong cricket tradition and very hospitable people. We like playing cricket here, but the presence of a small minority pursuing their own agendas at any cost will surely prevent tours for the foreseeable future. I sincerely hope that a solution can be found with time but assume Pakistan will first need a neutral venue solution for their home games.

Will I go back? When you have been through what we have experienced, when you have been targeted by terrorists yourself and been so fortunate to escape, it changes your thinking. It is a big question which cannot be answered now. I suspect, too, for us it can only be answered as an individual. Our families will never feel the same about us leaving to play in Pakistan. That is sad - for Pakistan and world cricket. [Link]

Monday, March 02, 2009

"Indian": Perhaps the most abused term in history

VS Naipaul explains why in his brilliant essay East Indian*:
…this word Indian has been abused as no other word in the language; almost every time it is used it has to be qualified. There was a time in Europe when everything Oriental or everything a little unusual was judged to come from Turkey or India. So Indian ink is really Chinese ink and India paper first came from China. When in 1492, Columbus landed on the island of Guanahani he thought he had got to Cathay. He ought therefore to have called the people Chinese. But East was East. He called them Indians, and Indians they remained, walking Indian file through Indian corn. And so, too, that American bird which to English-speaking people is the turkey is to the French, le dindon, the bird of India.

So long as Indians remained on the other side of the world, there was little confusion. But when in 1845 these Indians began coming over [as indentured laborers] to some of the islands Columbus had called the Indies, confusion became total...

But what were these immigrants to be called? Their name had been appropriated three hundred and fifty years before. “Hindu” was a useful word, but it had religious connotations and would have offended the many Muslims among the immigrants. In the British territories the immigrants were called East Indians. In this way, they were distinguished from the two other types of Indians on the islands: the American Indians and the West Indians. After a generation or two, the East Indians were regarded as settled inhabitants of the West Indies and were thought of as West Indian East Indians. Then a national feeling grew up. There was a cry of national integration, and the West Indian East Indians became East Indian West Indians.

This didn’t suit the Dutch. They had a colony called Surinam, or Dutch Guiana, on the north coast of South America. They also owned a good deal of the East Indies [Indonesia], and to them an East Indian was someone who came from the East Indies and was of Malay stock. (When you go to an Indian restaurant in Holland, you don’t go to an Indian restaurant; you go to an East Indian or Javanese restaurant.) In Surinam there were many genuine East Indians from the East Indies. So another name had to be found for the Indians from India who came to Surinam. The Dutch called them the British Indians. Then, with the Indian nationalist agitation in India, the British Indians began to resent being called British Indians. The Dutch compromised by calling them Hindustanis.
Hilarious, isn’t it?

*East Indian is an essay in the collection Literary Occasions, by VS Naipaul