Description
Question 1: Box Constrained Linear Program
A box-constrained linear program is a problem of the following form:
In other words, each variable xixi is constrained between lower limit lili and upper limit uiui. Given a box constrained LP, write down a linear time Θ(n)Θ(n) algorithm to find its optimal solution.
Answer (Expected Length: 3 lines)
Your answer here
Question 2: Budget Allocation Problem
There are nn communities in a city, C1,…,CkC1,…,Ck, with population P1,…,PkP1,…,Pk. The average daily income per capita for each community is given by I1,…,IkI1,…,Ik. The development budget BB dollars of the city is to be distributed between these communities following state law which stipulates the following constraints:
- The budget as a whole must be spent (no borrowing or saving allowed).
- The fair share fraction fifi for a community CiCi is defined as Pi∑kj=1PjPi∑j=1kPj.
- No community may receive an allocation that exceeds 1.1fiB1.1fiB or is lower than 0.9fiB0.9fiB.
- Let xjxj be the allocation for community CjCj. The overall allocation should be progressive to maximize the overall welfare formula given by ∑nj=1PjIjxj∑j=1nPjIjxj.
Formulate the budget allocation problem as a linear program.
Write down the LP for the data below. Use your favorite solver (Excel, GLPSOL, online solver) to solve the problem for the following data:
The total budget in millions is 5353 million.
Answer 2 (Expected Length: 6 lines)
Your answer here
Question 3: 0-1 Integer Linear Programming
A 0-1 integer linear program is an optimization problem involving binary variables x1,…,xn∈{0,1}nx1,…,xn∈{0,1}n as follows:
You may think of it as a linear program but with variables restricted to take on values in the set {0,1}{0,1}.
The 0-1 ILP problem takes as an input (a) description of the problem (variables, objectives and constraints) and (b) limit LL and decides whether there exists a solution for the variables satisfying the constraints such that the objective value ≥L≥L.
Show that 0-1 ILP problem is NP-Complete. (Hint Directly encode a 3-CNF-SAT clause as an inequality).
Answer (Expected Length: 10 lines)
Your answer here
Question 4: Independent Set
An independent set in a graph G=(V,E)G=(V,E) is a set of vertices I⊆VI⊆V such that each edge in EE is incident to at most one vertex in II. That is, an independent set is a set of vertices where no two vertices are adjacent.
The kk-independent set problem is to determine if a graph has an independent set of size at least kk.
(A) Show that the kk-independent set problem is NP-Complete by reducing from the 33-CNF-SAT problem.
(B) Show that the kk-independent set problem is NP-Complete by reducing from the kk-clique problem.
Answer (Expected Length: 10 lines)
Your answer here
