Archive for the ‘algorithms’ Category

I remember once, long ago in high school, there was some project where I had to look up and draw my family tree. Being the not-so-organized guy that I am, I lost that specific project many years ago. But since then, I also had a whole bunch of changes to the tree: I visited Iran […]

About a month ago, the Facebook Hacker Cup included a nice programming problem involving a certain kind of matching. The min-cost bipartite matching problem can be stated like this: You have a number P of people, and a number Q ≤ P of jobs. Each person is willing to do any of the jobs, but each person will charge a different price for each job. You are only allowed […]

Ravi Kannan gave a distinguished lecture today at Georgia Tech covering a wide swath of algorithms, randomness, and high-dimensional geometry. There was one particularly excellent slide that gave a very intuitive explanation for a result I have seen, but not fully understood, before. The result is in the field of streaming algorithms. Specifically, there is […]

I saw a nice result sketched a few weeks ago, on the “online matching” problem. Below I try to re-explain the result, using some idiomatic (and as a bonus, inoffensive) terminology which I find makes it easier to remember what’s going on. Online Matching. There is a set of items, call them Lunches, which you […]

I recently read a paper by Dughmi, Roughgarden, and Yan, which is a novel cousin of the Lavi-Swamy technique I taught last term. The latter is a way of turning linear program-based approximation algorithms into truthful-in-expectation mechanisms that approximately optimize expected social welfare. The main result of D-R-Y is in the same family: a truthful-in-expectation […]

Last week I was at an excellent summer school organized by TU Berlin and held at a nearby cottage/hotel. One topic that came up in a couple of talks was new to me: parametric search. First I’ll describe the setting and the basic result, due to Megiddo from 1979. In an optimization problem, we are […]

This week at EPFL I am presenting a recent paper by Andreas Björklund, which I found to be pretty elegant. It uses algebraic combinatorics to get a faster algorithm for a combinatorial problem: given a bunch of k-element subsets of {1, 2, …, kn},  determine if one can find a “perfect matching” of n subsets […]