CSG399 Home work 1

Xin Dong College of Computer Science

Northeastern University xindong@ccs.neu.edu

October 14, 2007

1 Stochastic matrices and LP duality

Let

M = ( m_{ij} )

Consider below LP: min 0 s.t. (I − M)\overline{x} = 0 \overline{1}^{T} \overline{x} = 1 \overline{x} ≥ \overline{0} Rewrite the above LP: min 0 s.t.

( \begin{matrix}I − M \\ \overline{1} & T \end{matrix} ) \overline{x} = ( \overline{0} 1 )

\overline{x} ≥ 0 Consider the dual of the above LP: max

\overline{y}^{T} ( \overline{0} 1 )

s.t.

\overline{y}^{T} ( \begin{matrix}I − M \\ \overline{1} & T \end{matrix} ) ≤ \overline{0}^{T}

Claim 1: The dual is feasible. Proof of claim 1: Let

y = ( \begin{matrix}y_{1} \\ y_{2} \\ . \\ . \\ . \\ y_{n} \\ y_{n+1} \end{matrix} )

And rewrite the dual as max y_{n+1} s.t. (y_{1}, ..., y_{n}, y_{n+1})A ≤ \overline{0}^{T} That is equivalent to (according to the definition of A) max y_{n+1} s.t. (y_{1}, ..., y_{n})(M − I) + y_{n+1}\overline{1}^{T} ≤ \overline{0}^{T} That is max y_{n+1} s.t. y_{n+1}\overline{1}^{T} ≤ (y_{1}, ..., y_{n})(I − M) The above LP is feasible because we can just let all y_{i}

except y_{n+1} equal to 1 and y_{n+1} equal to 0.

Claim 2: The dual is bounded. Proof of claim 2: Let y_{k} is the minimum value of all y_{i}

i = 1,...,n.

Then we have y_{n+1} ≤ y_{k} − ∑_{i=1}^{n} y_{i}m_{ik} ≤ y_{k} − ∑_{i=1}^{n} y_{k}m_{ik} = y_{k} − y_{k} ∑_{i=1} m_{ik} =0 Because the dual is feasible and bounded, the primal

is feasible and bounded. It is simple to check that the solution π of the primal satisfies Mπ = π and π is a probability vector.

2 Currency trading

2.1 a

Let N be the number of currency and T be the number of trading. Let C_{ki}, k = 1, ···, T, i = 1, ···, N be the number of the i^{th} currency after the k^{th} trading. Let C_{0i}, i = 1, · · ·N be the number of the i^{th} currency. Let Dollar be the first currency and Euros be the last currency. Obviously, C_{01} = D and C_{0i} = 0, i = 2, ⋯, N. Let t_{kij}, k = 1, ···, T, i, j = 1, ···, N be the number of the i^{th} currency that is changed to the j^{th} currency in the k^{th} trading. The LP for determining the collection of trades that will yield the maximum around of Euros for D US Dollars is: max C_{T N} s.t. C_{01} = D C_{0i} = 0, i = 2, ⋯, N t_{kij} ≥ 0 t_{kij} < l_{ij} C_{k−1 i} ≥ Σ_{j}t_{kij} C_{ki} = C_{k−1i} − Σ_{j}t_{kij} + Σ_{j}t_{kji}r_{ji} The constraint before the last one says that you must

have enough i^{th} currency in the trading.

The last constraint means that the amount of i^{th} currency after k^{th} trading is equal to the amount before trading minus the amount that is changed to other currencies plus the amount that is changed to i^{th} currency.

2.2 b

Proof: Suppose there are some cycles in the solution of the above problem that achieves the objective. We show that this solution can be changed to the one that achieves the objective without any cycle. The way is to remove the cycle one by one.

Consider any cycle from C_{mi} to C_{m+n i} in this solution such that t_{m+k p_{k}q_{k}} > 0, k = 1, ⋯, n, p_{1} = q_{n} = i and q_{k} = p_{k+1} ≠ i, k = 1, ⋯, n − 1.

First unify all t_{m+k p_{k}q_{k}} > 0, k = 1, ⋯, n to the i^{th} currency as t′_{m+k iq_{k}} = t_{m+k p_{k}q_{k}}/Π_{j=1}^{k−1}r_{p_{j}q_{j}}. Let k′ is the number such that t_{min} = t′_{m+k′ iq_{k′}} = min(t′_{m+k iq_{k}}, k = 1, ⋯, n).

Then modify the solution by changing t_{m+k p_{k}q_{k}} > 0, k = 1, ···, n as t′_{m+k p_{k}q_{k}} = t_{m+k p_{k}q_{k}} −t_{min}Π_{j=1}^{k−1}r_{p_{j}q_{j}}. Obviously t′_{m+k′ p_{k′} q_{k′}} = 0. By doing so, we actually push back some tradings that lead to the i^{th} currency.

Furthermore, modify the solution by changing C_{ki}, k = m + n, ⋯, T as C′_{ki} = C_{ki} + t_{min} − t_{min}Π_{j=1}^{n−1}r_{p_{j}q_{j}}r_{p_{n}q_{n}} = C_{ki} + t_{min}(1 − Π_{j=1}^{n}r_{p_{j}q_{j}}) ≥ C_{ki}.

The result solution is in accordance with the constraint of the original problem. In addition, it does not decrease the value of C_{T j}. So the result solution achieves our objective given the original one does so. By the above way, we remove the considered cycle. It is not difficult to see that we do not produce any new trading because we only push back some original tradings. So no new cycle is produced. Repeat the same way for each cycle one by one. Finally, we can remove all cycles while still achieve the objective.

2.3 c

Proof: Suppose there exist C_{T j} ≠ 0 for some j ≠ 1, N in the solution of the above problem that achieves the objective. By section b, we suppose the solution is acyclic.

Consider any C_{T j} ≠ 0, j ≠ 1, N, because initially we have only Dollars, there must be some trading chains that start from Dollars to the j^{th} currency. Following the method in section b, we must be able to remove any chain of this kind. In addition, no new trading is produced. Repeat the same way for each chain one by one. After all chains that lead Dollars to the j^{th} currency are removed, the result solution must satisfy C_{T j} = 0.

Repeat the above process for each C_{T j} ≠ 0, j ≠ 1, N one by one. Finally, we obtain the solution satisfies C_{T j} = 0, j = 2, ⋯N − 1.

In each step of the above process, C_{T N} does not change. So the result solution achieves the objective.

3 Analysis of an LP rounding algorithm for unweighted set cover

Hooman’s algorithm does not yield an O(logn) approximation even for uniform costs. Without loss of generality, suppose the elements of universe are numbered by 1, ⋯, n. Let k = \sqrt{n}. In order to explain the counterexample clearly, assume n = k^{2}. Construct the set of sets in this universe as follows. S_{1} = {1, ⋯, k} S_{2} = {2, ⋯, k + 1} · · · S_{k} = {k, ⋯, 2k − 1} S_{k+1} = {k + 1, ⋯, 2k} · · · S_{ik+j} = {ik + j, ⋯, (i + 1)k + j − 1} · · · S_{(k−1)k+1} = {(k − 1)k + 1, ⋯, n} S_{(k−1)k+2} = {(k − 1)k + 2, ⋯, n, 1} · · · S_{(k−1)k+j} = {(k − 1)k + j, ⋯, n, 1, ⋯, j − 1} In the above construction, j = 1, ⋯, k. Two properties

in the above construction are 1. Each element in universe appears in k sets.

2. The size of each set is k. Let all C(S_{i}) = 1, i = 1, ⋯, n. By property 2, we see that the optimal solution is to make x_{ik+j} = 0 for j ≠ k and x_{ik} = 1. The cost for the optimal solution is k. Consider LP: min Σx_{S} s.t. Σ_{S∈C:e∈S}x_{S} ≥ 1 ∀e ∈ U x_{S} ≥ 0 ∀S ∈ C. Claim 1: The solution of the above problem satisfies

that min Σx_{S} ≥ k.

Proof of claim 1: By the observation of the constraints, Σ_{j=1}^{n}x_{S_{ik+j}} ≥ 1 for all i = 0, ⋯, k − 1.

So min Σx_{S} = min Σ_{i=0}^{k−1}Σ_{j=1}^{n}x_{S_{ik+j}} ≥ min Σ_{i=0}^{k−1}1 = min k = k.

Claim 2: The lowest boundary k is reachable by let all x_{S_{i}} = 1/k for all i = 1, ⋯, n.

Proof of claim 2: It is simple to verify.

Consider this solution x^{∗}: x_{S_{i}} = 1/k, i = 1, ⋯, n. Sort the sets in nonincreasing order of x_{S}^{∗} values, the

possible sequence Σ can still be S_{1}, S_{2}, ⋯, S_{n}.

However, the smallest prefix of Σ that covers all the elements is S_{1}, S_{2}, ⋯, S_{(k−1)k+1}. So the cost is (k − 1)k + 1 following the Hooman’s algorithm. It is O(\sqrt{n}) approximation rather than O(logn) approximation.

4 A greedy algorithm for uncapacitated facility location

Proof of complexity: The greedy algorithm for this problem is at each step, pick the set with the smallest ratio of cost to newly covered elements, or, where U′ is the set of elements covered currently by the solution, find the set:

min_{s∈S} \frac{c(s)}{|s − U′|}

Let S_{1} denote the first set selected by the greedy algorithm, and let OP T denote the optimal solution. We claim that c(S_{1})/|S_{1}| is at most c(OP T)/n. This is because if every set S of the optimal solution had c(S_{i})/|S_{i}| exceed OP T/n, then the total cost of the optimal solution, which equals Σ_{s∈OP T} c(s) ≥ Σ_{s∈OP T} c(OP T)|s|/n = c(OP T)Σ_{s∈OP T} |s|/n ≥ c(OP T). Similarly if S_{2} is the second set selected by the greedy algorithm, then c(S_{2})/|S_{2}−S_{1}| is at most c(OP T)/(n−|S_{1}|). In general, if S_{i} is the i^{th} set selected by the greedy algorithm, then c(S_{i})/|S_{i}−⋃_{j<i} S_{j}| is at most c(OP T)/(n−| ⋃_{j<i} S_{j}|). Summing over all i, the cost of the greedy algorithm is at most

c(OP T)Σ_{i}|S_{i} − ⋃_{j<i} S_{j}|/(n − | ⋃_{j<i} S_{j}|) ≤ c(OP T)Σ_{i}1/(n − i) ≤ c(OP T)H_{n}.

Implementation in polynomial time: We manage to find

min_{X_{jS}} \frac{c(X_{jS})}{|X_{jS} − U′|}

in polynomial time.

In order to find the minimal ratio, fix j and consider any c(X_{jS}) for S ⊆ V. We have c(X_{jS}) = f_{j} + Σ_{i∈X_{jS}}d_{i}c_{ij} = f_{j} + Σ_{i∈X_{jS}∩U′}d_{i}c_{ij} + Σ_{i∈X_{jS}−U′}d_{i}c_{ij}. Then \frac{c(X_{jS})}{|X_{jS}−U′|} = (f_{j} + Σ_{i∈X_{jS}∩U′}d_{i}c_{ij} + Σ_{i∈X_{jS}−U′}d_{i}c_{ij})/|X_{jS} − U′| ≥ (f_{j} + Σ_{i∈X_{jS}−U′}d_{i}c_{ij})/|X_{jS} − U′| = (f_{j} + Σ_{i∈X_{jS}−U′}d_{i}c_{ij})/|X_{jS} − U′ − U′|. To find the minimal value, we need only check the set of form X_{jS} − U′, i.e., S ∩ U′ = ϕ.

In those sets that do not intersect with U′, fix the size of X_{jS}, c(X_{jS}) reaches minimum only when we pick X_{jS} that is closest to facility j, i.e., the minimal value of \frac{c(X_{jS})}{|X_{jS}−U′|} = \frac{c(X_{jS})}{|X_{jS}|} is achieved when we pick the first |X_{jS}| clients after all clients i ∉ U′ are sorted in nonincreasing order of the d_{i}c_{ij} value.

From the above analysis, the polynomial time algorithm to find

min_{X_{jS}} \frac{c(X_{jS})}{|X_{jS} − U′|}

is

v = +∞ rj = +∞ rk = ϕ for each j ∈ F sort all i ∉ U′ in nonincreasing order of the d_{i}c_{ij}

value for k = 1 to |V − U′| if ((f_{j} + Σ_{i≤k}d_{i}c_{ij})/k < v) v = (f_{j} + Σ_{i≤k}d_{i}c_{ij})/k rj = j rk = the set of first k elements in the ordered V −U′

return rj and rk

5 Multiset multicover problem

We introduce some denotations on the set in the finite universe U:

Element e occurs in a set s with arbitrary multiplicity, whose number is denoted by m(s; e).

Extend m to a denotation for the set s and the element from U as m(s; e) = 0 iff e ∉ s. Then the extended m(s; e) can be used to define s.

Define s_{1} ⋃ s_{2} as m(s_{1} ⋃ s_{2}; e) = m(s_{1}; e) + m(s_{2}; e). Define s_{1} ⋂ s_{2} as m(s_{1} ⋂ s_{2}; e) = min(m(s_{1}; e), m(s_{2}; e)). Define s_{1} − s_{2} as m(s_{1} − s_{2}; e) = max(0, m(s_{1}; e) − m(s_{2}; e)). Define |s| = Σ_{e∈U}m(s; e).

Define the set A as m(A; e) = r_{e}, i.e., the objective set. The greedy algorithm for this problem is at each step, pick the set with the smallest ratio of cost to newly covered elements, or, where U′ is the set of elements covered currently by the solution, find the set:

min_{s∈S} \frac{c(s)}{|s ⋂(A − U′)|}

Let S_{1} denote the first set selected by the greedy algorithm, and let OP T denote the optimal solution. We claim that c(S_{1})/|S_{1}| is at most c(OP T)/|A|. The reason is if every set S of the optimal solution had c(S_{i})/|S_{i}| exceed OP T/|A|, then the total cost of the optimal solution, which equals Σ_{s∈OP T} c(s) ≥ Σ_{s∈OP T} c(OP T)|s|/|A| = c(OP T)Σ_{s∈OP T} |s|/|A| ≥ c(OP T). Similarly if S_{2} is the second set selected by the greedy algorithm, then c(S_{2})/|S_{2} ⋂(A − S_{1})| is at most c(OP T)/(|A| − |S_{1}|). In general, if S_{i} is the i^{th} set selected by the greedy algorithm, then c(S_{i})/|S_{i} ⋂(A − ⋃_{j<i} S_{j})| is at most c(OP T)/(|A| − | ⋃_{j<i} S_{j}|). Summing over all i, the cost of the greedy algorithm is at most

c(OP T)Σ_{i}|S_{i} ⋂(A − ⋃_{j<i} S_{j})|/(|A| − | ⋃_{j<i} S_{j}|) ≤ c(OP T)Σ_{i}1/(|A| − i) ≤ c(OP T)H_{|A|}.

6 Selecting optimal views for a data warehouse

Some results come from the paper: Implementing Data Cubes Efficiently by Harinarayan, V.; Rajaraman, A.; Ullman, J. With some changes.

Here we are given a lattice < V, ⪯> of views v_{1}, v_{2}, ⋯, v_{n}. The number of rows (cost) for each view is r(v_{i}), i = 1, ⋯, n. and a lattice < Q, ⪯> of queries q_{1}, q_{2}, ⋯, q_{n}. That is isomorphic to < V, ⪯>.

For a sublattice < P, ⪯> of < V, ⪯> (precomputed views, include the top element T of < V, ⪯>), the cost C of < Q, ⪯> corresponding to < P, ⪯> is determined as the following.

For q_{i} ∈< Q, ⪯>, find the youngest ancestor A(v_{i}, P) of v_{i} in < P, ⪯>, the cost C(q_{i}) of q_{i} is r(A(v_{i}, P)).

C = Σ_{q_{i}∈Q}r(A(v_{i}, P)) denoted as C(< P, ⪯>).

Below we no longer make difference between q_{i} and v_{i}. The LP for the optimal views for a data warehouse is

described as following.

T is the top element of < V, ⪯>. Without loss of generality, let T = v_{n}.

r(v) is the cost of view v.

Let x_{i}, i = 1, ⋯, n denotes whether v_{i} ∈ P.

Let y_{ij}, i, j = 1, ⋯, n denotes whether query i can be answered by j.

All x_{i}, y_{ij} ∈ {0, 1}.

In our case, if v_{i} ⪯ v_{j} then y_{ij} ≤ x_{j}. That means query i can be answered by precomputed j if x_{j} = 1.

Otherwise y_{ij} = 0. That means i can never be answered by j no matter whether j is precomputed. Because we are maximizing the decrease, we relax the condition as y_{ij} ≤ 0.

In addition, we require Σ_{j}y_{ij} = 1 ∀i. The reason is that we are maximizing the decrease. Under the constraint that we can allow one precomputed j to answer i for each i, we won’t to include decreases from other ancestors of i. For the same reason as the above, we relax it as Σ_{j}y_{ij} ≤ 1

max Σ_{ij}y_{ij}(r(T) − r(v_{j}))

s.t.

Σ_{i}x_{i} = k + 1

x_{n} = 1

y_{ij} ≤ x_{j} ∀v_{i} ⪯ v_{j}; y_{ij} ≤ 0 otherwise

Σ_{j}y_{ij} ≤ 1 ∀i

The greedy algorithm of the above problem: After selecting some set S of views, the benefit of view v relative to S, which we denote B(v, S), is defined as follows. 1. For each w ⪯ v, define the quantity B_{w} by:

(a) Let u be the view of least cost in S such that w ⪯ u. Note that since the top view is in S, there must be at least one such view in S.

(b) If r(v) < r(u), then B_{w} = C(v) − C(u). Otherwise, B_{w} = 0.

2. Define B(v, S) = Σ_{w⪯v}B_{w}.

The greedy algorithm for selecting optimal views is: S = {T } for i=1 to k do begin

select that view v not in S such that B(v, S) is maximized;

S = S ⋃{v}; end; resulting S is the greedy selection;

To analyze the complexity of the above greedy algorithm, we introduce some denotations. Let v_{i}, i = 1, ···, k be the k views selected in order by the above algorithm. Let a_{i} be the corresponding benefit achieved by the selection of v_{i}. Let w_{i}, i = 1, ⋯, k be the optimal set of k views. We just pick an order. Let b_{i} be the corresponding benefit achieved by w_{i}. Define A = Σ_{i=1}^{k}a_{i} and B = Σ_{i=1}^{k}b_{i}.

Along with more and more views are selected, the improvement increases. For any view v, we can order the improvements in the same sequence that the views are chosen. For any view v, compare the improvements sequence of greedy algorithm with that of optimal solution. We can attribute each piece in optimal solution to some pieces in greedy algorithm. Define x_{ij} to be the sum over all views u in the lattice of the amount of the benefit b_{i} that is attributed to v_{j}.

First, the sum of the pieces of the benefit of v_{j} that is attributed to can’t exceed the benefit of v_{j}. That is Σ_{i=1}^{k}x_{ij} ≤ a_{j}.

Second, from our greedy algorithm, we have ∀i, b_{i} ≤ a_{i}. Furthermore, ∀i : b_{i} − x_{i1} ≤ a_{2}. The reason is that the benefit w_{i} brings to the competition for second choice is b_{i} minus the amount of benefit of w_{i} that was covered by v_{1}; the latter is x_{i1}. The benefit a_{2} must be at least as great as any competing choice. Generalizing the above , for each j we have ∀i : b_{i} − x_{i1} − ⋯x_{i,j−1} ≤ a_{j}.

So we get the family of inequalities: B ≤ ka_{1} B ≤ ka_{2} + a_{1} · · · B ≤ ka_{k} + a_{1} + ⋯ + a_{k−1} Consider any e_{i} ≥ 0, i = 1, ⋯, k. We have e_{1}B ≤ e_{1}ka_{1} e_{2}B ≤ e_{2}ka_{2} + e_{2}a_{1} · · · e_{k}B ≤ e_{k}ka_{k} + e_{k}a_{1} + ⋯ + e_{k}a_{k−1} Sum left and right respectively, we have (Σ_{i}e_{i})B ≤ (e_{1}k + e_{2} + ⋯e_{k})a_{1}+ (e_{2}k + e_{3} + ⋯e_{k})a_{2}+ · · · (e_{k−1}k + e_{k})a_{k−1}+ e_{k}ka_{k} Let e_{k} = 1/k, e_{k−1} = (1 − 1/k)/k, ⋯e_{i} = (1 −

e_{i+1} − ⋯ − e_{k})/k = (1 − 1/k)^{k−i}/k, i = k, ⋯, 1. We make coefficients of a_{i} in the right be all 1. The left side is (1/k + (1 − 1/k)/k + ⋯ + (1 − 1/k)^{k−1}/k)B.

So (1 − (1 − 1/k)^{k})B ≤ A. The greedy algorithm is 1/(1 - 1/e)-approximation when k is large enough.

7 Approximation factor for the LP deterministic rounding algorithm

Some results come from lecture notes: FacLocFiltering.pdf. Change step 2 of algorithm 1, let r_{i} = \frac{4}{3}Σ_{j}x_{ij}^{∗} × c_{ij}.

Claim 1 is changed to: ∀i ∈ V, Σ_{j∈B_{i}}y_{j}^{∗} ≥ \frac{1}{4}. Lemma 1 is changed to: Let LP_{F} denote the facility

cost of the LP solution. Then, Σ_{j∈F′}f_{j} ≤ 4 × LP_{F}.

Lemma 2 is changed to: Let LP_{i} be the service cost of client in the LP solution. Then, ∀i ∈ V, c_{iσ(i)} ≤ 4 × LP_{i}.

Let LP_{S} denote the service cost of the LP solution. Then Lemma 2 gives us Σ_{i}c_{iσ(i)} ≤ 4 × LP_{S}.

All above results can be proved by the same way in the lecture notes except some changes on the coefficients when estimating the left side or the right of inequalities. Then it is almost trivial to achieve new Theorem 2:

T otalCost ≤ 4 × (LP_{F} + LP_{S}).

8 Another 4-approximation LPbased algorithm for uncapacitated facility location

(a) Proof: We want to show that c_{kσ(k)} ≤ 3v_{i}^{∗}. According to our algorithm, there are two cases:

1. σ(k) = j_{k}. Then x_{kj_{k}}^{∗} > 0. By complementary slackness conditions, v_{k}^{∗} − w_{kj_{k}}^{∗} = c_{kj_{k}}. So v_{k}^{∗} ≥ c_{kj_{k}} = c_{kσ(k)}.

2. ∃j, k such that x_{ij}^{∗} > 0, x_{kj}^{∗} > 0 and σ(i) = j_{k}. Then c_{iσ(i)} = c_{ij_{k}} ≤ c_{ij} + c_{jk} + c_{kj_{k}} = c_{ij} + c_{kj} + c_{kj_{k}}. Because x_{ij}^{∗} > 0, v_{i}^{∗} − w_{ij}^{∗} = c_{ij} by complementary slackness conditions. Similarly, v_{k}^{∗} − w_{kj}^{∗} = c_{kj}. In addition, c_{kj_{k}} ≤ v_{k}^{∗} by the discussion of case 1. So, c_{ij} + c_{kj} + c_{kj_{k}} ≤ v_{i}^{∗} + v_{k}^{∗} + v_{k}^{∗}. Because v_{k}^{∗} is the least in U, v_{k}^{∗} ≤ v_{i}^{∗}. Then we have c_{iσ(i)} ≤ 3v_{i}^{∗}.

(b) Proof: Consider any k where j_{k} is added to F in step 2 of our algorithm. We have f_{j_{k}} = min{f_{j} : x_{kj}^{∗} > 0} ≤ Σ_{j:x_{kj}^{∗}>0}f_{j}x_{kj}^{∗} ≤ Σ_{j:x_{kj}^{∗}>0}f_{j}y_{j}^{∗}. Assume k′ is added to F after some time. We know that ∀j if x_{k′j}^{∗} > 0, then x_{kj}^{∗} = 0. Otherwise k′ will be removed from U after k is handled. So {j : x_{kj}^{∗} > 0} ⋂{j : x_{k′j}^{∗} > 0} = Φ. Then we have Σ_{k}f_{j_{k}} ≤ Σ_{k}Σ_{j:x_{kj}^{∗}>0}f_{j}y_{j}^{∗} ≤ Σ_{j}f_{j}y_{j}^{∗}.

(c) Proof: COST = Σ_{k}f_{j_{k}} + Σ_{i}c_{iσ(i)} ≤ Σ_{j}f_{j}y_{j}^{∗} + 3Σ_{i}v_{i}^{∗} = Σ_{j}f_{j}y_{j}^{∗}+3(Σ_{j}f_{j}y_{j}^{∗}+Σ_{ij}x_{ij}^{∗}c_{ij}) ≤ 4(Σ_{j}f_{j}y_{j}^{∗}+ Σ_{ij}x_{ij}^{∗}c_{ij}).

9 Hardness of the non-metric kmedian problem

Some results come from the paper: Inapproximability of the Asymmetric Facility Location and k-Median Problems by Aaron Archher. With some changes.

Proof: Suppose we have polynomial-time algorithm P KM with an approximation ratio c^{n}(c > 1). We are given set cover problem < S, E > where E is a ground set and S a collection of subsets of E. Here let m = |S| and n = |E|. We can construct the k-Median problem below in polynomial time:

Let N = m + n and M = c^{N}m.

Let F = S and C = S ⋃ E. Let c_{i_{1}i_{2}} = 1 for i_{1}, i_{2} ∈ F. For i ∈ E, j ∈ S, let c_{ij} = 0 whenever j covers i, and c_{ij} = M otherwise. We still assume demand is all 1. (Unit demand). This forms a k-Median problem given any k.

Consider the algorithm below:

for k=1 to m run P KM if the cost of P KM < M

return k and facilities chosen return -1 By observation, if t is the size of the optimal set cover,

then the k-Median problem with input t has optimal solution with the cost (m − t). Meanwhile, the k-median problem with any input that is less than t has optimal solution with the cost that is at least M.

So if t is the size of the optimal set cover, our algorithm will loop until t because the cost of P KM is at least M for k < t. Then our algorithm will return at k because at that time, the cost of P KM is at most c^{N}(m − k) < M.

On the other hand, if our algorithm returns t and facilities chosen, then we know the size of the optimal set cover is not in [1, t−1]. Otherwise, the cost of P KM is at most c^{N}(m − k) < M at some k ∈ [1, t − 1] and our algorithm should return at that time.

Finally, if the cost of P KM < M at some t, the facilities chosen is a cover of size t. The reason is no client with cost M. So all client in E is assigned to one facility with cost 0. That is ∀i ∈ E, ∃j ∈ F, j covers i. So the facilities chosen (the number is t) covers E.

So we get a polynomial-time algorithm for set cover problem. That is P = NP because set cover problem is NP − Complete.

10 Maximum satisfiability and randomized rounding

Some results come from: The Probabilistic Method by Sariel Har-peled. With some changes

(a) Proof: Let I_{true} be the assignment that all variables are true and I_{false} be the assignment that all variables are false. Consider any clause C_{j}, j = 1, ⋯, m. C_{j} is satisfied by either I_{true} or I_{false}. The reason is for any variable v_{i}, i = 1, ⋯, n in C_{j}, if it appears in the positive, C_{j} must be satisfied by I_{true}. If it appears in the negative, C_{j} must be satisfied by I_{false}.

So the total number of clauses satisfied by either I_{true} or I_{false} is at least m. Then, we have either the number of clauses satisfied by I_{true} or the number of clauses satisfied by I_{false} is at least m/2. The algorithm has an approximation factor of 2.

(b) For any clause C_{j}, let z_{j} ∈ {0, 1} be a variable indicating whether C_{j} is satisfied or not. Similarly, let x_{i} = 1 if the v_{i} variable is being assigned the value T RUE. Let C_{j}^{+} be indices of the variables that appear in C_{j} in the positive and C_{j}^{−} be indices of the variables that appear in C_{j} in the negative. Clearly, to solve MAX-SAT, we need to solve:

max Σ_{j=1}^{m}z_{j}

s.t.

x_{i}, z_{j} ∈ {0, 1} ∀i, j

Σ_{i∈C_{j}^{+}}x_{i} + Σ_{i∈C_{j}^{−}}(1 − x_{i}) ≥ z_{j} ∀j

We relax this into the following linear program:

max Σ_{j=1}^{m}z_{j}

s.t.

x_{i}, z_{j} ∈ [0, 1] ∀i, j

Σ_{i∈C_{j}^{+}}x_{i} + Σ_{i∈C_{j}^{−}}(1 − x_{i}) ≥ z_{j} ∀j

(c) Proof: Consider any clause C_{j} with k literals l_{t}, t = 1, ⋯, k. For any l_{t}, if it is the positive appearance of some variable v_{i_{t}}, then l_{t} is satisfied with the probability x_{i_{t}}^{∗}. If it is the negative appearance of some variable v_{i_{t}}, then l_{t} is satisfied with the probability that is equal to the probability that x_{i_{t}} is assigned F ALSE, that is 1 − x_{i_{t}}^{∗}. So C_{j} is not satisfied with the probability Π_{i∈C_{j}^{+}}(1 − x_{i}^{∗})Π_{i∈C_{j}^{−}}x_{i}^{∗}. Then C_{j} is satisfied with the probability P r[C_{j}]

= 1 − Π_{i∈C_{j}^{+}}(1 − x_{i}^{∗})Π_{i∈C_{j}^{−}}x_{i}^{∗}

≥ 1 − ((Σ_{i∈C_{j}^{+}}(1 − x_{i}^{∗}) + Σ_{i∈C_{j}^{−}}x_{i}^{∗})/k)^{k}

= 1 − ((k − (Σ_{i∈C_{j}^{+}}x_{i} + Σ_{i∈C_{j}^{−}}(1 − x_{i})))/k)^{k}

≥ 1 − ((k − z_{j}^{∗})/k)^{k} = 1 − (1 − z_{j}^{∗}/k)^{k} ≥ (1 − (1 − 1/k)^{k})z_{j}^{∗} ≥ (1−(1−1/L)^{L})z_{j}^{∗} where L is the maximum number

of literals in a clause.

Therefore, the expected number of clauses satisfied is Σ_{j}P r[C_{j}] ≥ Σ_{j}(1 − (1 − 1/L)^{L})z_{j}^{∗} = (1 − (1 − 1/L)^{L})Σ_{j}z_{j}^{∗} ≥ (1 − (1 − 1/L)^{L})OP T.

(d) Proof: In order to analyze the algorithm, we consider the more detailed description.

v = Φ (v is the assignment of variables: 0 is false; 1 is true)

while |v| < n Assume v has the form (v_{1}, ⋯, v_{l}) v_{0} = (v_{1}, ⋯, v_{l}, 0) v_{1} = (v_{1}, ⋯, v_{l}, 1) if (E_{v_{0}} < E_{v_{1}}) v = v_{1}

else v = v_{0}

Assume that the randomized algorithm in c choose v_{0} with probability p_{0} and v_{1} with probability p_{1}. Then, E_{v} = p_{0}E_{v_{0}} + p_{1}E_{v_{1}} ≤ max_{i}E_{v_{i}}. And so, by choosing the v_{i} that maximizes the expectation E_{v_{i}}, we are still guaranteed a good approximation. Repeat this step over and over, the value of the guaranteed expectation does not decrease.