Sunday, October 18, 2009

A Counterexample

Several of you have proposed algorithms for problems 2, 3 and 4 based on the following idea: (1) find a matching, (2) remove the matching from the graph, (3) continue after modifying the problem.



I claimed that that wouldn't work except for some very special cases (for example, in bipartite graphs this works for some versions of the problem). Here's a very simple example to show that you have to do something completely different. The figure on the left shows a graph whose edges are colored, thus forming a decomposition into three matchings. On the right is a partial coloring of the same graph, showing a single perfect matching. If your algorithm is based on the idea described above, there will be no way to prevent the first matching from being this one. The problem is that the remaining uncolored edges cannot be split into two matchings.



Hint for all of the questions 2, 3 and 4: change the problem! Reduce it to a single problem you do know how to solve, not to an iteration where you cannot control how the sequence of problems you're solving behaves.

Tuesday, October 13, 2009

Slides on matching

Hi professor

I cannot find the slides for matching in the blackboard, would you please post it? Thank you.

Tuesday, September 29, 2009

Study/discussion group?

Would anyone be interested in forming a recurring weekly study group to go over topics covered in class?

Natalie

Class Audio Recordings

Hey! Someone asked in class if the professor could audio record the class and post it online. I happened to have my MP3 player on me, so I decided to try out its recording functionality! I figure I'll just keep updating this post, rather than making a new one every lecture. It'll be cleaner this way.

For the first recording, I just had the recorder sitting on my desk. So the quality was a bit lacking. The other[s?] though, is much better.

Tuesday 9/29/09
Thursday, 10/1/09

Let me know how these sound, and if they're helpful and stuff.

Later,
-Alt

Creative Commons License

Friday, September 25, 2009

Hw3, question 4

It seems this question has confused some of you. Here's an example that was sent in by a student and that I've tried explaining. Consider the matrix A=[ [0,1,0], [2,0,3], [4,0,5] ]. (It doesn't matter if in this notation, the rows are listed first or the columns...)

In this matrix, you can choose entries 1 in row 1, column 2, then 2 in row 2, column 1, and finally 5 in row 3, column 3. You thus have three nonzero entries, no two of which are in the same line.

So if the statement is going to be correct, you also need to show that whatever two lines (rows or columns) you choose, you'll miss at least one nonzero entry. This is clear for such a small matrix.

Now take a different example: B=[ [0,1,0], [1,0,1], [0,1,0] ]. Picking the nonzeros in row 1, column 2 and in row 2, column 1 gives two nonzeros that are not in the same line. However, we cannot add to this either of the other two nonzeros without having two nonzeros either in one row or in one column.

On the other hand, we cannot cover all the nonzeros with just one line, but need at least two (the middle row and the middle column). Thus both the maximum and the minimum are equal to 2.

I hope this helps, but do respond if there is still something that is not clear.

Thursday, September 24, 2009

Multiterminal flows

I've uploaded another handout related to Gomory-Hu trees on the Blackboard site. This is a Chapter from the classical book Flows in Networks by Ford and Fulkerson. In it, you'll find some background and motivation for cut- and flow-equivalent trees.
It also contains a worked-out example of the algorithm so you can make sure you understand it.

While scanning this today, I realized that we've pretty much covered most of the topics discussed in this book: maximum s-t flows, minimum s-t cuts, minimum-cost flows and circulations, and now Gomory-Hu trees. Of course, many details have changed in the almost 50 years since the book was written. For example neither Edmonds-Karp nor Goldberg-Tarjan algorithms were known as such then. The minimum mean cycle paper is also more than 15 years younger than the book. Also, there are many details and a few different viewpoints that the book covers that we haven't gotten to yet.

After we wrap up Gomory-Hu trees, we'll proceed to matchings and then some linear and integer programming to expose the duality between some pairs of problems that we've studied already.

Further questions

I referred to two things in class today as good candidates for questions on the next homework.

The first was about finding the minimum mean cycle. Suppose you modify edge costs by subtracting a constant from each. If the constant is just right (exactly the minimum mean cycle cost), then the minimum mean cycle will now have cost 0. If the constant is just a bit larger, the same cycle will have cost that is just a bit negative. How can you set the constant so that you are sure only the minimum mean cycle(s) will have negative cost?

The second question relates to what I claimed about flow-equivalent trees in undirected graphs. I claimed that there was always a flow equivalent path. Think about building a flow-equivalent tree (there are simpler algorithms than the one we discussed in class because you don't have to worry about cut equivalence) and see what you could do to make the algorithm build a path.

Another Hw3 correction

In question 2, I wanted to ask about the maximum number of different values for minimum s-t cuts.

(In other words, if you can find an example with more than n-1 different mincut values, then you'll know that a flow tree cannot exist for such a graph.)

Actually, even without the missing word, the question makes sense. It's just that the number could conceivably be much higher because each subset of vertices might define a cut of different capacity.

Answering this second variant will result in at least some credit.

Thursday, September 17, 2009

Homework 3

What was the correction on Homework 3 mentioned in class today? I lost my notes on this during the day...

Tuesday, September 8, 2009

Proof for Shortest augmenting path. Let f be augmented into g.
Let d_f(v)>d_g(v) be the contradiction we wish to refute.

We assume that the v was the first vertex that whose shortest distance was reduced by augmentation. By first vertex i mean first along that path, not the first augmentation in the algorithm itself. This is by the assumption for above contradiction.----------------1

Let there be an edge (u,v) that was on the augmented path g. (u,v) in E_g. Where E_g is the edge set of path g.
d_g(u)=d_g(v)-1 ------- 2
Because the path to v must cross through u.
d_g(u)>=d_f(u) ------- 3
Because if d_g(u)<d_f(u) then the distance to u could have been the first on the path g that was reduced violating Assumption 1. So u should have been atleast as much as it was before...


If we can somehow prove that (u,v) was not in E_f... Then we can say that there was no predecessor of v that could have been chosen such that we had a path to augment in the first place. And therefore no such path can exist. This is a sufficient thing to do to prove our point.

(You may argue that (u,v) can only come on g after the augmentation. That is possible if u was a bottleneck earlier and was reversed to reach v. That is ok, what I am just saying here is that no such edge (u,v) existed earlier. )

Now Let E_f be the edge set of path f. Let (u,v) be an edge in E_f (We will refute this in a while).
Now Using this I can say:
d_f(v)<=d_f(u)+1. Otherwise u is not parent of v and there are more edges between u and v... So Just pick a u that is parent..Doesnt matter which...
=> d_f(v)<=d_f(u)+1<=d_g(u)+1 --- By 3 above
=> d_f(v)<=d_f(u)+1<=d_g(u)+1 =d_g(v) -- Equality because u->v is an edge on g....
=> d_f(v)<=d_g(v)
Which is Contradiction, so no such (u,v) exists in E_f such that we could get an augmenting path g...




Saturday, September 5, 2009

Homework 2

hi, Just to clarify some doubts. In Q1 part a, we assume the min cut= max flow and just improve an existing max flow algorithm for the answer?. Also do we need to find the cut set, in addition to the value?

Tuesday, September 1, 2009

Homework 1 clarifications and hints

Hint for question 1: the goal is to count trees, but it turns out to be easier to count sequences. These two things will be equivalent if only we can show that the algorithm given in the question can be reversed.

In question 2, it makes more sense to assume the graph is directed. (Otherwise every edge is both incoming and outgoing.)

In question 3, the running time requested is large enough to first run any of the three minimum spanning tree algorithms we've discussed in class, so you may as well assume that the optimal tree is given at the beginning of your algorithm without increasing the overal running time.

Question 6 is an example of something we'll study later in the course, where we will be able to relate a maximization and a minimization problem by studying their structure.

Thursday, August 27, 2009

Introductory

Welcome! I've set up this blog in order to allow you to ask questions and exchange ideas related to the course CSE 550 Combinatorial Algorithms and Intractability, Fall 2009.

Please follow the instructions from my email and sign up to be able to comment and post.

Feel free to ask questions through comments or to create new posts whose topics are related to the course material. Appropriate posts may include: (1) questions about specific topics/problems discussed in class (for example, requests for clarification), (2) questions about course material based on your own readings (for example, you've read something on algorithms in a book or on a website that you'd like help with understanding), (3) questions asking for clarification of homework problems. Please don't ask for or post complete solutions to homework problems.