PeCoWriMo derail

Well I got slightly distracted from my PeCoWriMo project. No particularly good reason – I was just feeling a bit disenchanted with the subject matter and Haskell was annoying me slightly (as usual). Nothing enough to actually derail me on it’s own, but I got to thinking about a problem I’d worked on before and decided to do some more work on it.

And in keeping with the mild irritation with Haskell and the “oh for the love of god anything but more ruby” I decided to do it in another nicer, friendlier language.

Err, that is to say, C.

The problem this is working on is that of finding a minimal feedback arc set in a weighted graph (although I’ve actually posed it as a maximization problem). This boils down to the following problem:

Given N points and a weight function w(x, y) find an enumeration x_1, …, x_N that maximizes sum_{i < j} w(x_i, x_j) The main application I care about is voting, but I'm sure it has other uses. Code is available on github

This entry was posted in Uncategorized on by .