Archive for the ‘algorithms’ Category

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 […]

Consider the following network design problem. Schmoogle‘s 100 offices want to be able to stream huge amounts of data to each other (e.g., to broadcast talks to all their offices). In order to do this they need to connect all of their offices with new Phlogiston-net cabling. A single cable can be used to connect […]