Category Archives: combinatorial optimization

ACO in Python: Minimum Weight Perfect Matchings (a.k.a. Matching Algorithms and Reproductive Health: Part 4)

This is the final item in my series on Matching Algorithms and Reproductive Health, and it brings the story full circle, returning to the algorithms side of the show. Today I’ll demonstrate how to actually find minimum-weight perfect matchings in Python, and toss in a little story about \pi^2/6. Continue reading


Filed under combinatorial optimization

Matching Algorithms and Reproductive Health: Part 3, A Stylized Virginity Pledge

It’s been three weeks and one IHME retreat since I wrote about matching algorithms and virginity pledges, and I think I now understand what’s going on in Patient Teenagers well enough to describe it. I’ll try to give a stylized example of how the minimum-weight perfect matching algorithm makes itself useful in reproductive health research.

I think it’s helpful to focus on a concrete research question about the virginity pledge and its effects on reproductive health. Here’s one: “does taking the pledge reduce the chances that an individual contracts trichomoniasis?” If the answer is yes, or if the answer is no, people can still argue about the value of the virginity pledge programs, but this seems like relevant information for decision making. Continue reading


Filed under combinatorial optimization, global health

Matching Algorithms and Reproductive Health: Part 2, Matching and Virginity Pledges

I might have been a little over-ambitious with this series. I wrote a little bit about the how matching theory emerged from the social sciences two weeks ago. But then I got really busy! And that was the part I actually knew something about ahead of time. The promised connection between matching algorithms and reproductive health (and more generally, how matching is being used in quasi-experiment design) is the part that I have to do some reading on before I can write knowledgeably about.

However, I have a plan: I’d like to “crowd-source” my library research. Continue reading


Filed under combinatorial optimization, global health

Matching Algorithms and Reproductive Health: Part 1, Matchings Emerge from Social Science

Earlier this week, I was inspired by current events to launch a bold, crazy-sounding series about matching theory and its application to reproductive health.  This first installment is a quick social history of the development of matching theory, largely influenced by (and fact-checked against) Lex Scrijver’s encyclopediac Combinatorial Optimization: Polyhedra and Efficiency.  His paper “On the history of combinatorial optimization (till 1960)” contains similar information in an easy-to-download form.

On to the story:  how social science applications drove the  development of matching theory. Continue reading


Filed under combinatorial optimization, global health

Matching Algorithms and Reproductive Health: Part 0

One of the first things on Obama’s agenda after being sworn in as President last week was lifting the “global gag rule”, a Regan-era innovation that tied US aid to strict anti-choice regulations. Meanwhile, the TCS reading group at UW has been studying matching problems and Edmond’s blossom algorithm. Together, this has been the motivation I needed to launch a series of posts about applications of matchings in reproductive health metrics. Part 1 will have more about matchings.

1 Comment

Filed under combinatorial optimization, global health, videos

Busy Week

Friday, already! Happy fragile ceasefire in Gaza, happy wedding to Daniel and Anna, happy Martin Luther King Day, and happy presidential inauguration.
I pass by this mural of MLK almost every day, and I find it incredibly expressive. Maybe it has something to do with the Seattle weather. Today I thought he was looking tired, but hopeful.

Maximum 1-out from search results graph of politicians and corporationsIs there some research paper out there to distract me from thinking about politics too much?  How about a networks paper with applications to politics?  An Arxiv paper from the Physics and Society section was updated recently, and it caught my eye with some beautiful pictures. I’ll explain a little, or you can head straight for their figure on the interactions between presidential candidates and corporations. Continue reading

Comments Off

Filed under combinatorial optimization

ACO in Python: PADS for Minimum Spanning Trees

Sometimes, instead of working, I like to see what search terms are bringing readers to my blog. The most common search that healthyalgorithms has been most useless for is “minimum spanning tree python”. Today, I’ll remedy that.

But first, dear searchers, consider this: why are you searching for minimum spanning tree code in python? Is it because you have a programming assignment due soon? High-school CS class is voluntary. All college is optional, and many you are paying to attend. You know what I’m talking about? Perhaps the short motivational comic Time Management for Anarchists is better than some Python code.

Still want to know how to do it? Ok, but I warned you.

Continue reading


Filed under combinatorial optimization

Best of the Year

I didn’t make any best-of-the-year lists, but I support the idea. I also support new year’s resolutions, but I’m not going to write about mine.

But the internet picks up the slack.

FlowingData has a 5 Best Data Vis of the year list, which I’m fond of. It includes the beautiful Streamgraphs of Byron and Wattenberg. Their technical report has some fun applications of combinatorial optimization to aesthetics.

Streamgraph at the box office

Lance Fortnow has a nice Complexity Year in Review on the Computational Complexity Blog. Unfortunately, I don’t have a beautiful illustration of Prasad’s result that Unique Games Conjecture implies semidefinite relaxations have optimal approximation ratios.


Filed under combinatorial optimization, general, TCS

Combinatorics of Malaria Eradication

Malaria infecting a mosquito

I’ve got at least 3 interesting blog posts worth of material on TCS applications for fighting malaria, but I haven’t had time to pen even one of them. Here is an abbreviated version:

Malaria is a major disease, something like the #3 infectious disease globally, and the #1 cause of both death and disability in many parts of Southern Africa.

The Gates Foundation is leading the charge to attempt to eradicate malaria from the world, and many national governments and NGOs are also involved in the fight.

There is a history of malaria eradication attempts, and the historic lesson is this: don’t start a fight with malaria unless you’re going to win.

Continue reading

1 Comment

Filed under combinatorial optimization, global health, TCS

Learning to Rank

A lovely stats paper appeared on the arxiv recently. Learning to rank with combinatorial Hodge theory, by Jiang, Lim, Yao, and Ye.

I admit it, the title is more than a little scary. But it may be the case that no more readable paper has so intimidating a title, and no more intimidatingly titled a paper is more readable.

Continue reading

Comments Off

Filed under combinatorial optimization, probability