You are currently browsing the monthly archive for February 2011.

See also the mouse-over text on this strip.

*In which we look at the linear programming formulation of the maximum flow problem, construct its dual, and find a randomized-rounding proof of the max flow – min cut theorem.*

In the first part of the course, we designed approximation algorithms “by hand,” following our combinatorial intuition about the problems. Then we looked at linear programming relaxations of the problems we worked on, and we saw that approximation algorithms for those problems could also be derived by rounding a linear programming solution. We also saw that our algorithms could be interpreted as constructing, at the same time, an integral primal solution and a feasible solution for the dual problem.

Now that we have developed exact combinatorial algorithms for a few problems (maximum flow, minimum s-t cut, global min cut, maximum matching and minimum vertex cover in bipartite graphs), we are going to look at linear programming relaxations of those problems, and use them to gain a deeper understanding of the problems and of our algorithms.

We start with the maximum flow and the minimum cut problems.

*In which we show how to solve the maximum matching problem and the minimum vertex cover problem in bipartite graphs.*

*In which we begin to discuss the Arora-Rao-Vazirani rounding procedure.*

Recall that, in a graph with adjacency matrix , then ARV relaxation of the sparsest cut problem is the following semidefinite program.

If we denote by the optimum of the relaxation, then we claimed that

where the first inequality follows from the fact that is a relaxation of , and the second inequality is the result whose proof we begin to discuss today.

*In which we describe a randomized algorithm for finding the minimum cut in an undirected graph.*

- Justin Bieber’s
*dad*is younger than me; - The New York Times writes that “While the younger generation is losing interest in blogging, people approaching middle age and older are sticking with it.”

*In which we prove that the basic implementation of the push-relabel algorithm runs in time .*

*In which we prove that the Edmonds-Karp algorithm for maximum flow is a strongly polynomial time algorithm, and we begin to talk about the push-relabel approach.*

When I got a computer for my new office at Stanford last year, it came with the Apple wireless keyboard, a piece of equipment that some people like very much, and that has a handsome and minimalist design. The bluetooth connection was, however, occasionally flaky, and it seemed silly to have a battery operated device sitting in front of a desktop. So I decided to buy a wired keyboard instead, and since everybody raves about how good it is to type on Lenovo laptops, I thought Lenovo would sell a keyboard made to feel like their laptops. Unfortunately there does not seem to be such a thing.

Searching for information about keyboards, however, I found a whole online cult devoted to the keyboards that IBM made for its PC in the 1980s: the IBM Model M keyboard. Although I never owned or used an IBM PC, I remember using similar keyboards when I was a graduate student in the mid 1990s, and we each had a terminal on our desk connected to a mainframe in the basement. The terminals had monochromatic, text-only, displays, but they keyboards were good, and, every time you would press a key, they would go *CLICK*, just like the 1980s IBM keyboards. (The terminals were made by HP and were 1980s technology.)

The license/patents to make these keyboards went to Lexmark, when IBM spun off its printers/devices business. Making the keyboards, however, was not profitable because *they never break* — see for example this video of a Model M versus a watermelon.

Lexmark then sold the license/patents to Unicomp, an American company whose business is to make clones of the IBM Model M keyboard and other 1980s models.

So that’s what I got for my office and, while I feel rather self-conscious about showing enthusiasm about a keyboard, it is *awesome*. (To be precise, the keyboard I got is not an exact clone of the IBM model M: mine has a USB cable, a “Windows” key, and it works with a Mac without drivers. The Windows key becomes the “command” key. For the purists, it is possible to buy actual IBM models M, with a PS/2 interface which can be connected to a USB via converter, at clickykeyboards.com, where they even have “mint condition never used” ones.)

This term, as readers of *in theory* might have noticed, I am writing notes for two classes, which means that I am typing for roughly 15-20 hours a week, mostly at home. Usually, at home I would work using the laptop on the sofa, and use my desk for storage, but this wasn’t good this term, so I (mostly) cleared the desk, got a monitor, a mouse, another, *awesome* Unicomp keyboard, and hooked it all up to my MacBook Air (which has new hinges, yay!). Read the rest of this entry »

## Recent Comments