Monthly Archives: January 2009

January 29, 2009 · 7:58 pm

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 →

6 Comments

Filed under combinatorial optimization, global health

Tagged as , , , ,

January 27, 2009 · 9:04 pm

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

Tagged as , , ,

January 23, 2009 · 6:43 am

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 on Busy Week

Filed under combinatorial optimization

Tagged as

January 15, 2009 · 7:36 pm

Big News Day for Industrial TCS

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.

1 Comment

Filed under TCS

Tagged as , ,

January 13, 2009 · 7:08 pm

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 →

10 Comments

Filed under combinatorial optimization

Tagged as , , ,

January 9, 2009 · 7:29 pm

On Gaza

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 →

7 Comments

Filed under general

January 5, 2009 · 5:59 pm

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.

3 Comments

Filed under combinatorial optimization, general, TCS

Tagged as , , , ,