Unformatted text preview:

Name:Date:MA 515, Linear Programmingand Combinatorial OptimizationFall 2008, Final ExamThere are 150 possible points. You are not allowed to use your book ornotes.12Problem 1: (30 points) First, describe the main themes of this courseand their interactions. Second, choose a theorem that you feel excellentlyrepresents these themes and do the following:(1) State the theorem;(2) Give an example of the theorem in action; and(3) Explain why you chose this theorem, specifically addressing how itrelates to the main themes you described in the first part.3Problem 2: (40 points) Consider the following five contexts in whichwe have a “max=min” result.(1) Linear programming(2) Greedy algorithm for matroids(3) Matroid intersection(4) Bipartite matchings(5) Matchings in general graphsChoose four of these and make a precise statement of the “max=min” resultin each case. Sketch the proof for one of these, indicating clearly which oneyou have chosen.4Complete four of the following five problems, each worth 20points.Problem 3a: Consider the following matrix:A :=−1 −1 −1 01 0 0 −10 1 0 00 0 1 1Let M be the linear matroid determined by A. Provide a description of thematroid polytope for M as an H-polytope, and use linear programming tofind a maximal independent set in M .5Problem 3b: Construct a graph G on 6 vertices with 9 edges. Assign toeach of these edges a distinct positive weight. Choose a specific vertex, labelit v, and use Dijkstra’s algorithm to find all minimum-weight v − w-dipathsin G.6Problem 3c: Let G be a planar graph. Take any planar embedding ofG and form the planar dual G∗. Prove that the graphic matroid of G∗isthe dual of the graphic matroid of G.7Problem 3d: Let G be a graph with no loops and no multiple edges.Prove that a matching S of G is of maximum cardinality if and only if Ghas no augmenting path with respect to S.8Problem 3e: Given two matroids M1and M2on a common groundset E and an independent set S ∈ I(M1) ∩ I(M2), define the bipartiteaugmentation digraph for S and explain its role in the Cardinality Matroid-Intersection


View Full Document

UK MA 515 - MA515 Final Exam

Download MA515 Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MA515 Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MA515 Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?