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
Today there are headlines from almost all of the computer companies with TCS research labs. Some sounds good, some sounds bad. How this will affect research?
This seems like a fine time to mention the Post-Graduate Fellowship Program at IHME (app deadline March 1, 2009). It would be fun to have more TCS people up here.
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 need a break from the health and algorithms posts for a second, to include something about the situation in Palestine. For the last two weeks, the hot war has been on my mind too much. I can’t keep writing about math movies and python tutorials without acknowledging it. Continue reading
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.