Monthly Archives: January 2015
A couple of comments about today’s lecture: 1) Here’s a nice example (from Michel Goemans’ notes) of an instance where the max-matching is of size 8. Can you find such a matching? Can you find some set such that the … Continue reading
We didn’t get time to see Fredman’s “trick” after all. What Fredman shows in this paper is the following result: The min-sum product (MSP) of two matrices can be computed using only comparisons. (He uses instead of our .) Using … Continue reading
And it’s on the webpage. 3 problems. Due next Friday. Please ask questions/clarifications here, or in office hours. [Edit: I added in a problem at the end, that you don’t have to submit, but may find interesting to solve if … Continue reading
Two things I wanted to re-emphasize about today’s lecture: Yu asked, “where does the algorithm use the undirectedness”? The undirectedness was used in the Claim 2 towards the end. In particular, for the first part of the claim, we used … Continue reading
Just to clarify, today in lecture we only showed that for every non-negative cost function, there is an optimal solution to the LP that is an r-arborescence. It is not true if we allow negative costs, because nothing in our … Continue reading
I’ve put down my office hours for Monday 3-4pm. However, since next Monday is MLK Day, this week I’ll have office hours Friday — the day after tomorrow at 3-4pm (right after class).