Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 360 Fall 2023

Assignment 3

Due: Thursday, November 2nd, 2023 at 8:00pm

1. Question: Consider the following linear program.              [10]

min                 3x1 + 2x2 − 4x3 − 10x4

subject to                       x1 + 2x3 + x4 ≥ 10

                                         −2x3 − 3x4 ≥ −12

                                   −x2 + 5x3 + x4 ≥ 20

                                  2x2 − 3x3 − 3x4 ≥ −36

                                       x1, x2, x3, x4 ≥ 0

a. Write down the dual of this linear program.                  [5]

b. The optimal solution to this linear program is (0, 0, 4.5, 1). Use this optimal solution and the complementary slackness conditions to find an optimal solution for the dual linear program.             [5]

2. Question: A bakery creates three different products: fruit pies, bread, and chocolate cakes. It is trying to plan out how to buy common ingredients in order to maximize its revenue. The ingredients required to make, and the revenue generated by selling, one unit of each product is recorded in the following table:                                  [15]

                          Flour       Butter      Sugar     Milk      Fruit      Chocolate     Yeast      Revenue

Fruit Pie              500 g      250 mL      150 g    0 mL      500 g         0 g              0 g            $20

Bread                 250 g       25 mL        0 g       0 mL       0 g           0 g              50 g            $8

Chocolate Cake    300 g      150 mL      250 g     300 mL   0 g           250 g           0 g            $30

The bakery starts off with the following amounts of each ingredient:

                  Flour          Butter        Sugar         Milk            Fruit          Chocolate        Yeast

Amount      50,000 g      5,000mL     15,000g    30,000mL    20,000g          5,000g            1,000g

a. Suppose you are running a rival bakery, and you want to buy all of the ingredients that the above bakery currently has. In order to do so you must set a price for each ingredient. However, the above bakery will not sell you its ingredients immediately (you are a rival, after all). In fact, it will only sell the ingredients to you if it can make at least as much money selling the ingredients to you as it would have made if it baked the ingredients into goods and sold the goods for profit.

Write a linear program that will find the optimal setting of prices for each ingredient (i.e. flour, butter, sugar, milk, fruit, chocolate, yeast) so that the first bakery will sell you all of its ingredients, but, so that you will minimize the amount you spend to buy the ingredients. Your linear program should have one variable for each ingredient, representing the price of buying one unit of that ingredient (e.g. $/gram, etc.). Briefly justify the definition of your linear program.            [10]

b. Prove that the minimum cost to buy all ingredients from the first bakery is equal to the maximum profit that the original bakery could make by baking its ingredients into goods and selling them.            [5]

3. Question: Give a polynomial-time reduction from SAT to the following problem. Given a boolean formula F which has 2n variables appearing in it, denoted x1, x2, . . . , xn, y1, y2, . . . , yn, decide if F has a satisfying assignment (x, y) where additionally x1 = y1, x2 = y2, . . . , xn = yn.       [10]

4. Question: For each of the following variations on the Vertex Cover problem, either prove that the variation is in P by giving a polynomial-time algorithm solving it, or, give a polynomial-time reduction from Vertex Cover to that variation. Briefly justify that your algorithms and reductions are correct.            [30]

(a) Given a graph G, decide if it is possible to delete no more than 100 edges from G such that the resulting graph has a vertex cover of size 10.

(b) Given a graph G and two positive integers d, k, decide if it is possible to delete d edges from G such that the resulting graph has a vertex cover of size at most k.

(c) Given a graph G and a positive integer k, decide if the smallest vertex cover on G has size at most k.

(d) Given a graph G with at most 1, 000 vertices and a positive integer k, decide if G has a vertex cover of size k.

(e) Given a tree T and a positive integer k, decide if T has a vertex cover of size at most k.

(f) Given two graphs G1 = (V1, E1) and G2 = (V2, E2), define a new graph G1 ∨ G2 as follows. The vertices of G1 ∨ G2 are ordered pairs of vertices (v1, v2) ∈ V1 × V2 — for instance, if V1 = {a, b} and V2 = {1, 2} then V1 × V2 = {(a, 1),(a, 2),(b, 1),(b, 2)}. The edges of G1 ∨ G2 are defined as follows. An edge ((u1, u2),(v1, v2)) is in G1 ∨ G2 if and only if either (u1, v1) ∈ E1 and u2 = v2, or, (u2, v2) ∈ E2 and u1 = v1.

The variation of vertex cover is then as follows. Given G1, G2, and a positive integer k, decide if G1 ∨ G2 has a vertex cover of size at most k.