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 . Continue reading
Category Archives: combinatorial optimization
ACO in Python: Minimum Weight Perfect Matchings (a.k.a. Matching Algorithms and Reproductive Health: Part 4)
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
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
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
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.
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.
Is 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
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.
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.
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.
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.
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.