5 Relaxing Integer Linear Programs As discussed in lecture, Integer Linear Programming (ILP) is NP-complete. In this problem, we discuss attempts to approximate ILPs with Linear Programs and the potential shortcomings of doing so. Throughout this problem, you may use the fact that the ellipsoid algorithm finds an optimal vertex (and corresponding optimal value) of a linear program in polynomial time. (a) Suppose that x0 is an optimal point for the following arbitrary LP: maximize c x subject to: Ax b x 0 Show through examples (i.e. by providing specific canonical-form LPs and optimal points) why we cannot simply (1) round all of the element in x0, or (2) take the floor of every element of x0 to get good integer approximations. (b) The Matching problem is defined as follows: given a graph G, determine the size of the largest subset of disjoint edges of the graph (i.e. edges without repeating incident vertices). Find a function f such that: maximize f subject to: X eE,ve xe 1 v V 0 xe 1 e E is an LP relaxation of the Matching problem. Note that the ILP version (which directly solves Matching) simply replaces