CSC373-Assignment 3 Solved

Assignment 3

Q1Auction Optimization
Suppose there is a marketplace with S suppliers, C customers and G goods. Supplier i supplies at most Sik units of good k and asks for $Aik price per unit of good k. customer j demands at most Djk units of good k and bids $Bjk per unit of good k. Imagine that you are the auctioneer: you collect all the pricing and bidding information, then allocate supplies to customers. You would be making profit of an amount equal to the absolute difference between the bidding price $Bjk and the asking price $Aik for every unit of good k sold by supplier i to customer j.

(a)Provide an LP formulation to maximize your profit.

(b)Suppose supplier i and customer j are not at the same location and the available fleet capacity allows for transportation of at most Uij goods from supplier i to customer j. In addition you incur a cost of Cij per unit of any good transported from supplier i to customer j. Provide an LP formulation to maximize market clearing profit under these additional conditions.

(c)Suppose that the fleet capacities Uij of (b) are given in terms of kilograms and each good k weighs Wk kilograms. Modify your formulation to (b).

Q2Minimizing Maximum Deviation
Linear programming is often used to solve statistical problems. We consider two examples here. We are given n data points (xi,yi) and wish to find a line of best fit y = ax+b for some coefficients a,b that best approximates the behaviour of the data points. The l∞ distance between a point (xi,yi) and a line y = ax + b is defined as the quantity |yi − axi − b|.

(a)Suppose we want to minimize the l∞ error for the line of best fit, defined as the maximum of l∞ distance over the set of data points. Give a linear program that will produce a line of best fit with minimum l∞ error.

(b)In the classification problem, you are given m data points of type 1 and n data points of type 2. We say that a line y = ax + b separates the points all data points of type 1 satisfy yi < axi + b and all data points of type 2 satisfy yi > axi + b. Give a linear program that will determines if there is a line that separates the points, and if one exists, maximizes the gap δ defined as max(e1,e2), where ei is the minimum l∞ distance between the line and points of type i.

1

Q3Nearly-SAT
Nearly-SAT is the problem described as follows:

Input: A CNF Formula F over n variables x1,...,xn and having m clauses

Output: “Yes” if there is an assignment of the variables x1,...,xn that satisfies exactly m−1 clauses, “No” otherwise

(a)Show that Nearly-SAT is in NP.

(b)Given a CNF formula F over the variables x1,...,xn and which has m clauses, construct a CNF formula F0 over the same set of variables and which has two additional clauses (so m + 2 in all) such that an assignment to the variables x1,...,xn that satisfies all m clauses of F satisfies precisely m + 1 clauses of F0.

(c)Use part (b) to give a polynomial time reduction from SAT to Nearly-SAT and show that Nearly-SAT is NP-hard.

Q4Tile Covering
An architect is given a set of rectangular tiles ti, each with some length li and width wi (li ≥ wi). There is a wall with length l and width w, and the architect would like to see if there is a way to cover the wall with tiles so that each tile is placed horizontally or vertically, there are no overlaps between the tiles or gaps on the wall, and furthermore each tile is placed on the wall. Assume that all dimensions are given as rational numbers.

(a)The Architect problem is defined as the following decision problem: given the tiles and the dimensions of the wall, is there a way to cover the wall according to constraints? Show that the Architect problem is in NP.

(b)Show that the Architect problem is NP-Complete. You may assume that the following problem is NP-Complete:

Partition:          Given a set of positive integers S that sum to n, is there a subset S1 ⊆ S that sums to  ?

2