$1\mathrm{.}4.$ Do you agree that Greedy can achieve an approximation ratio of $2?$ If yes, please add your

proof; otherwise, offer a specific example of vertex cover to disapprove it$.(5$ Points$)$

You run a small business out of New York and Boston. You are a small operation and need to

be close to where the most customer demand is in a month: so$,$ in each month, you either work

from New York or from Boston $($exactly one of these two options$).$ Based on forecasted demand,

you know that in month $i,$ you will incur an operating cost of $N_i>0$ if you work from New York in

that month, and $B_i$ if you work from Boston that month. You need to plan ahead for your locations

for the next $n$ months: if you change locations from month $i$ to $i+1($where $1in-1),$ you

incur a fixed moving cost of $M.$

$2\mathrm{.}1$ Given $n,M,$ and the $N_i$ and $B_i$ values, develop an algorithm running in time polynomial in $n$

that finds a plan of least total cost for the next $n$ months $-$ a plan of where to operate from for each

of these $n$ months. Please write down the pseudo codes formally following the style you see in the

homework. $(15$ points$)$

$2\mathrm{.}2.$ Apply your algorithm in $2\mathrm{.}1$ to this instance: $n=5,M=8,N=(N_i)=(10,9,20,8,15),$ and

B $=(B_i)=(5,25,7,17,9),$ and output the results. Note that the final output should specify clearly

in each month $1i5,$ you should stay at which of the two locations, New York or Boston, and

the total resulting cost. $(15$ points$)$

In the class, we have discussed in detail Greedy for Coverage Maximization Problem $($COV$-$

MAX$).$

$3\mathrm{.}1.$ Consider such an instance as follows: $n=6,m=4,$ and $k=2,$ where the groundset

is $G=[n]=\{1,2,$dots,$6\},$ the collection of subsets is $C=\{S_j|jin[m]\}$ with $S_1=\{1,2,3,4\},$

$S_2=\{2,3,5\},S_3=\{1,4,6\},S_4=\{1,3,6\}.$ Please compute the following: $(1)$ The collection of

subsets output by Greedy and the corresponding coverage; $(2)$ An optimal solution and the related

coverage, and the resulting approximation ratio of Greedy on the specific instance. $(15$ Points$)$

$3\mathrm{.}2.$ Can you create another instance of MAX$-$COV such that the approximation ratio achieved

by Greedy on the instance is strictly less than what is shown above $($i$.$e$.,$ on the instance given in

$3\mathrm{.}1)?$ Please state clearly your instance and related analysis to support your claim. $(10$ Points$)$

$3\mathrm{.}3.$ Recall that in class, it was demonstrated that the Greedy algorithm achieves an approximation

ratio of $1-\frac{1}{e}$~~$0\mathrm{.}632$ for MAX$-$COV. This implies that for any instance of MAX$-$COV, the coverage

of the solution produced by Greedy is at least a fraction of $1-\frac{1}{e}$ of the optimal solution's coverage.

Can you construct an instance illustrating that the approximation ratio of $1-\frac{1}{e}$ is indeed tight?

In simpler terms, can you create an example where the ratio between the coverage achieved by

Greedy and the optimal coverage approaches, or can be made arbitrarily close to$,1-\frac{1}{e}?(5$

Points$)$