Let G = (V, E) be an undirected graph. An independent set of G is a...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Let G = (V, E) be an undirected graph. An independent set of G is a subset V' c V such that, for every edge e = {u, v} e E, at most one of u and v is in V'. We are interested in constructing an independent set of maximum size. In this variant there are no weights on the vertices. There is a natural Integer Linear Program (ILP) for this problem, which has |V| binary variables and one functional constraint per edge. a. (3 points) Write down the natural ILP for this problem, and its LP-relaxation. b. (3 points) Explain briefly why, in the LP-relaxation, constraints of the form 0 ≤ x ≤ 1 can be replaced by 20 without changing the feasible region of the LP-relaxation. c. (4 points) Let P be the version of the LP-relaxation in which constraints 0 ≤ x ≤ 1 have been replaced by , 20. Write down the dual of P. Call this D. d. (5 points) Let K₁, be the complete graph on n vertices i.e. the graph where every vertex is connected to every other vertex. Using the dual D and any other arguments you think relevant, prove the following: for every n ≥ 2, the optimum value of the ILP when applied to Kn, divided by the optimum value of the LP-relaxation when applied to Kn, is exactly 1/(n/2) = 2/ Let G = (V, E) be an undirected graph. An independent set of G is a subset V' c V such that, for every edge e = {u, v} e E, at most one of u and v is in V'. We are interested in constructing an independent set of maximum size. In this variant there are no weights on the vertices. There is a natural Integer Linear Program (ILP) for this problem, which has |V| binary variables and one functional constraint per edge. a. (3 points) Write down the natural ILP for this problem, and its LP-relaxation. b. (3 points) Explain briefly why, in the LP-relaxation, constraints of the form 0 ≤ x ≤ 1 can be replaced by 20 without changing the feasible region of the LP-relaxation. c. (4 points) Let P be the version of the LP-relaxation in which constraints 0 ≤ x ≤ 1 have been replaced by , 20. Write down the dual of P. Call this D. d. (5 points) Let K₁, be the complete graph on n vertices i.e. the graph where every vertex is connected to every other vertex. Using the dual D and any other arguments you think relevant, prove the following: for every n ≥ 2, the optimum value of the ILP when applied to Kn, divided by the optimum value of the LP-relaxation when applied to Kn, is exactly 1/(n/2) = 2/
Expert Answer:
Answer rating: 100% (QA)
a The ILP is Maximize sumv in V xv subject to for each edge uv in E xu x... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these general management questions
-
Let G = (V, E) be an undirected graph with subset I of V an independent set. For each a I and each Hamilton cycle C for G, there will be deg (a) - 2 edges in E that are incident with a and not in C....
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Find a function (x, y) such that = (y, x).
-
Knowing that the radius of each pulley is 200 mm and neglecting friction, determine the internal forces at point K of the frame shown. 18 m 0.2 m 0.6 m 0.8 m 0.2 m 360 N
-
(i) Why does profit continue to be the preferred basis for evaluation of the financial performance of a business? (ii) In what ways can cash flow provide a better basis for performance evaluation,...
-
Why is monitoring and information disclosure critical for the success of emissions banking and trading?
-
Willard Motors, Inc., employs 20 sales personnel to market its line of luxury automobiles. The average car sells for $65,000, and a 6 percent commission is paid to the salesperson. Willard Motors is...
-
Market Analysis Group LLC offers specialized surveys to companies that do not have internal marketing research staff. A typical survey involves three activities: survey proposal and design, data...
-
From Exercise 10A-3, prepare a schedule of accounts payable and verify that the total of the schedule equals the amount in the controlling account. Exercise 10A-3:
-
a. What is a leap second and why is it used? b. Explain in detail about external data and marshaling in a distributed system. c. Demonstrate the design requirements for distributed architectures.
-
Galiano Company carried out the following transactions related to its common and preferred shares. The following transactions were carried out during Year 1 : January 1 Issued 8 , 0 0 0 common shares...
-
Factory overhead of $44,700 consists of Indirect labor of $21,900, Depreciation expense-Factory of $16,900, and Factory utilities of $5,900. a. Compute total manufacturing costs. b. Prepare a...
-
QUESTION 5 (20 MARKS) The following is a report of a clinical trial to evaluate the efficiency of maintenance Chemotherapy for acute Leukemia. Patients were randomly allocated to group 1 and II....
-
Find the intervals of increasing and decreasing for: f(x) = x4-2x3
-
QUESTION TWO (20 MARKS) Consider a discrete random variable taking values 0, 1, 2, 3,... Find E(T) as a function of the survivor function. Hence find the mean of the random variable whose survivor...
-
A company manufactures and sells two products, S1 and S2. The total annual sales is expected to be R630 000 with a sales mix of 2:3 respectively. The contribution margin ratio of Product $1 is 40%,...
-
Cassandra Casey operates the Futuristic Antique Store. She maintains subsidiary ledgers for accounts payable and accounts receivable. She presents you with the following information for October 2019:...
-
Give a (n)-time non recursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
-
Which is asymptotically larger: lg(lg n) or lg (lg n)?
-
In how many ways can n professors sit around a circular conference table? Consider two seatings to be the same if one can be rotated to form the other.
-
Applying the criterion for equilibrium, derive the Clausius-Clapeyron equation.
-
A binary liquid mixture consists of \(60 \mathrm{~mol}\) per cent ethylene and \(40 \mathrm{~mol}\) per cent propylene. At \(423 \mathrm{~K}\), the vapour pressure of ethylene and propylene are...
-
The pure component vapour pressure of two organic liquids \(\mathrm{X}\) and \(\mathrm{Y}\) by Antoine equations are given by \[ \ln P_{1}^{\text {Sat }}=14.35-\frac{2942}{T+220} \] and \[...
Study smarter with the SolutionInn App