Category Archives: combinatorial optimization

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 on Learning to Rank

Filed under combinatorial optimization, probability

Minimum Spanning Trees of Bounded Depth (Random)

I’ve got a new paper up on the arxiv.  David Wilson recently posted this joint work that was one of the last things I did during my post-doc at Microsoft.  It hasn’t been applied to health metrics yet, but maybe it will be.  Let me tell you the story:

A spanning tree is just what it sounds like, if you know that a tree is a graph with no cycles, and make a good guess that the spanning tree is a subgraph that is a tree “spans” all the vertices in the graph.  Minimum cost spanning trees come up in some very practical optimization problems, like if you want to build a electricity network without wasting wires.  It was in this exact context, designing an electricity network for Moravia, that the first algorithm for finding a minimum spanning tree was developed.

Public Domain image of a Minimum Spanning Tree, from Wikipedia

A Minimum Spanning Tree, from Wikipedia

The great thing about looking for a minimum spanning tree is that you don’t have to be sneaky to find it.  If you repeatedly find the cheapest edge which does not create a cycle, and add that to your subgraph, then this greedy approach never goes wrong.  When you can’t add any more edges, you have a minimum spanning tree.  Set systems with this property have been so fun for people to study that they have an intimidating name, matroids.  But don’t be intimidated, you can go a long way in matroids by doing a search-and-replace s/matroid/spanning tree/.

Continue reading


Filed under combinatorial optimization, probability