复杂度理论4

Posted on Edited on

3.1

Lema: $_{i=1}^{k+1}v_iOPT $

Proof:考虑fractional背包问题的解\(OPT'\),显然\(OPT' \geq OPT\),同时，由于分数背包贪心算法，\(OPT' \leq \sum\limits_{i=1}^{k+1}v_i\)，引理得证.

因此 \((\sum\limits_{i=1}^{k}v_i)+v_{k+1} \geq OPT\),故而 \(\sum\limits_{i=1}^{k}v_i\),\(v_{k+1}\)二者必有其一比一半\(OPT\)大.

3.3

首先，如果对于一组解，存在一个无法在due time前完成的job出现在一个在due time完成的job之前，交换他们使得答案不劣。因此肯定有一个最优解使得所有及时完成的job先被执行

其次，对于两个及时完成的job:\(i,j\)，如果 \(d_i \geq d_j\) 并且\(i\)比\(j\)早开始，交换他们使答案不劣，因此最终可以看出他们都是按照截止时间排序的。

可以给出如下dp：

1
2
3
4
5
6
7
8
sort all the jobs according to their due time in ascending order
s[0]={(0,0)}
for i=1 to n:
    s[i]=s[i-1]
    for j in s[i-1]:
        if j[0]+p[i]<=d[i]:
            s[i].insert((j[0]+p[i],w[i]+j[1]))
    delete all the dominant pairs in s[i]

FPTA近似算法：

令\(\mu=\frac{M\epsilon}{n}\)（其中\(M=max(w_i)\)） 令 \(w'_i=\lfloor\frac{w_i}{\mu}\rfloor\)

设对\(\{w'_i\}\)进行dp得到的解为\(I\),原问题中\(OPT\)的解为\(O\) \(\mu \sum\limits_{i \in I}w'_i \geq \mu\sum\limits_{i\in O}w'_i \geq (\sum\limits_{i \in O}w_i)-n\mu=OPT-M\epsilon \geq (1-\epsilon)OPT\)

复杂度为 \(O(n\cdot n\frac{M}{\mu})=O(\frac{n^3}{\epsilon})\)

3.5

3.6

先考虑关于值域的dp： 

1
2
3
4
5
6
7
8
seq=topsort(G)
for u in seq:
    S[u]={}
    for v in pre(u):
        for (x,y) in S[v]:
            if x+l(v,u)<=L:
                S[u].add((x+l(v,u),y+c(v,u)))
    eliminate all the dominant pairs in S[u]

上述算法的时间复杂度是 \(O((n+m)C)\), 考虑rounding

令 \(c'_e=\lceil \frac{c_e}{\mu} \rceil\)

在\(c'_e\)的图上跑上述dp，假设跑出来的边集是\(I\),原问题最优解边集是 \(O\) , \(\sum\limits_{e \in O}c_e=OPT\)

\(\sum\limits_{e \in I}c_e \leq \mu \sum\limits_{e \in I}c'_e \leq \mu \sum\limits_{e \in O}c'_e \leq \sum\limits_{e \in O}c_e+\mu |O| \leq OPT+m\mu\)

取 \(m\mu=C_{min} \cdot \epsilon\)

\(OPT+m\mu \leq OPT+C_{min} \cdot epsilon \leq (1+\epsilon)OPT\)

复杂度是\(O((n+m)\frac{C}{\mu})=O(\frac{(n+m)m}{\epsilon})\)