CS 4301 — Special Topics in Computer Science: Optimization, Homework 1
Problem 1;
I have read and understand the policies on the course website.
Let be an undirected graph, let be a matching in , and let . In class, we saw an time algorithm to compute an -augmenting path if one exists. Now, suppose we know is bipartite and connected. Describe an time algorithm to find an -augmenting path or report that no such path exists. Hint: What happens if you run the algorithm for general (non-bipartite) graphs? Will you find an -flower?
Since is bipartite, denote the two sets of the bipartition . Note that any -augmenting path must start and end different sides of the graph, as it is of odd length and there are no edges where and no edges by definition of a bipartite graph. Observe that an -blossom must be of odd length, must begin and end with an edge which is not contained within the matching, and must be a cycle (by the definition of an -blossom).
This implies that no blossoms can exist in the graph, as in order to start and end on vertex (a cycle), it must start and end in the same set, which requires an even number of edges.
For our algorithm, we must also observe that we do not have enough time to construct a new bipartite graph. As we BFS to try to find an augmenting path from initial vertex , maintain a counter , where is at most the length of the longest path found. If is odd, only consider adjacent edges which are not in the matching. If is even, only consider adjacent edges which are in the matching.
If an odd length path exists from , then it is an augmenting path. Otherwise, no augmenting path exists from .
BFS can take at most .
Argue that one can compute a maximum matching in a bipartite graph in time
Since there are at most augmenting paths in the graph, and finding each augmenting path takes , the entire algorithm takes
Problem 2; Recall, any polyhedron can be written as the Minkowski sum of a polytope Q and its characteristic cone . In other words, .
Let . Prove that for any and for any , we have
Start with a point
with
. This is allowed, since P can be written as the Minkowski sum. Note that and for and
Distributing, this means that . This means that , and thus there is a point
Argue that polyhedron is unbounded if and only if its characteristic cone contains at least one non-zero point.
If ‘s characteristic cone contains at least one non-zero point (let’s take an arbitrary one called ), then for the bounded polyhedron , there is a point from which a ray of arbitrary length beginning at a point which is contained within the polygon. However this means that given radius for bounding the polyhedron, for the vector will not be contained within the ball. This contradicts that the polyhedron is bounded.
For the other direction, if is unbounded, then it suffices to show that there is a non-zero vector for which . Assume for simplicity that is unbounded only along a single hyperplane. This is a safe assumption, since any larger unbounded regions are simply an infinitely large set of hyperplanes. In other words, there is some direction in which we can walk forever. In this hyperplane, we may take any vector of arbitrary length (and any ) parallel to the hyperplane, which is also contained within the hyperplane, and is thus contained in .
Problem 3; Prove the following variant of Farkas’ lemma. Let and . The system , has no solution if and only if there exists some such that , , and . Advice: Modify the proof of the original variant of Farkas’ lemma at the bottom of the Lecture 5 notes on the class website. We’ll go through that proof on Monday, February 10th.
Following the lecture notes,
expresses , , with as the identity matrix.
By the Theorem of alternatives, the system is not feasible iff there is a , where and such that
From the second inequality, , and thus for this holds.
We must then show that if there exists some such that , , and , then , has no solution.