Write an lp for the mst problem

Assignment Help Computer Engineering

Reference no: EM132105046

This problem is about the minimum spanning tree (MST) problem in an undirected graph, where every edge has a non-negative cost.

(a) Write an LP for the MST problem, which enforces the constraint that at least one edge is selected from every cut. Show that you can solve this LP in polynomial time by using an efficient separation oracle.

(It is sufficient to identify the problem you need to solve in the separation oracle; you do not need to give an explicit algorithm.)

Give an example to show that this LP is not integral. (Recall that an LP is said to be integral if there is at least one optimal solution where all the variables take integer values.)

(b) Write a different LP for the MST problem where you enforce an upper bound on the number of edges selected from any induced subgraph, and a lower bound on the total number of edges. Show that any integral feasible solution to this LP is a spanning tree of the graph.

Reference no: EM132105046

Questions Cloud

Ratio on reserve set : If a bank holds an access reserve of $8000 and the checkable deposits are at $150000 and the ratio on reserve set at 20%?

How much are the budgeted purchases for? november : Beginning inventory for November $47000 and ending inventory for November is estimated at $53000. How much are the budgeted purchases for? November?

Create an employee object using the constructor : Write another main function to answer the following parts. Only submit the main function for this problem.

Predetermined overhead rate-various cost drivers : The following data pertain to the Oneida Restaurant Supply Company for the year just ended.

Write an lp for the mst problem : Write an LP for the MST problem, which enforces the constraint that at least one edge is selected from every cut.

Exploitation of labor and resources : What is meant by the concept of fair trade referencing to the exploitation of labor and resources?

What is the net operating income for the month : I do not know where to go after this?? What is the net operating income for the month under absorption costing?

What is the company margin of safety in dollars : What is the company's margin of safety in dollars?

Write a class that verifies that a password meets : Write a class that verifies that a password meets the stated criteria. Demonstrate the class in a program that allows the user to enter a password.

User Account

All Pages