Algorithm Design 7
NP-Hardness
NP Completeness : Decision Problem
NP Hardness : Optimization Problem
Problem in NP-Hard : not in NPC , but the decision version is NPC
How to almost solve NP-Hard problem ?
- Special Restrictions
- Approximation
- Randomization
Chapter 5 Extending the Limits of Tractability
Solving NP-Hard problem under some special restrictions
Max Independent Set
- general graphs : NP-Hard
- interval graph : P
- tree / graph with bounded tree width : P
FPT (fixed parameter tractable)
Intuition : Consider the parametrization of an instance
Def [ FPT ]: Input size \(n\) , parameter \(k\) . A problem is FPT if there exists an algorithm that solve the problem in \(\mathcal O(f(k)poly(n))\).
\(k\) can be viewed similar to constant , \(\mathcal O(2^kpoly(n))\) is still FPT , but \(\mathcal O(n^k)\) is not FPT ( \(poly(n)\) is independent from \(k\) ).
Vertex Cover , \(k=|VC|\)
We want to construct an algorithm in \(\mathcal O(f(k)poly(n))\) , which is better than trivial algorithm in \(\mathcal O(n^{k})\) .
Key Observation : \(e=(u,v)\) , \(VC(G)\le k\iff VC(G-u)\le k-1\lor CV(G-v)\le k-1\) .
Algorithm : check \((G,k)\)
- If \(G\) has no edge , then the
empty set is a VC , return
true
. - If \(|E|> k|V|\) , then \(\not\exists VC,|VC|\le k\) , return
false
. - Let \(e=(u,v)\in E\) , return
check(G-u,k-1)||check(G-v,k-1)
.
- If \(G\) has no edge , then the
empty set is a VC , return
Running time : By recursive tree , at most \(k\) levels , level \(i\) has \(2^{i-1}\) possibilities , with \(\mathcal O(n(k-i+1))\) computation in each node.
Total time : \(\mathcal O(2^kkn)\) .
Best FPT : \(\mathcal O(1.2738^kpoly(n))\) .
Method : reduce more in Key Observation (e.g. \(k\to k-1\) improve to \(k\to k-2\)) by considering more edges.
Kernel method : \(\mathcal O(|E|+(5^{1/4})^k k^2)\) .
Chapter 6 Approximation Algorithm
6.1 Approximation Criteria
Approximation ration \(\alpha\ge 1\)
minimization problem : \(\alpha:=\sup_I \frac{SOL(I)}{OPT(I)}\).
maximization problem : \(\alpha:=\sup_I \frac{OPT(I)}{SOL(I)}\).
Some examples
- Exact solution : \(\alpha=1\)
- Constant approximation : \(\alpha=\mathcal O(1)\)
- Logarithm approximation : \(\alpha=\mathcal O(\log n)\)
- \(\alpha=\mathcal O(n)\) : usually not interesting.
- Poly-Time Approximation Scheme ( PTAS ) : \(\alpha=1+\epsilon\) , Time : poly when \(\epsilon\) is constant.
- Fully Poly-Time Approximation Scheme ( FPTAS ) : Time : \(\mathcal O(poly(\frac{1}{\epsilon},n))\).
6.2 Load Balancing Problem
Description :
Input : \(n\) jobs , \(t_i\) : time for job \(i\) , \(m\) machines
Output : assign each job to one machine , say machine \(j\) is assigned jobs \(S_j\) , minimize \(\max_{j=1}^m \left\{\sum_{i\in S_j}t_i\right\}\) .
Load Balancing Problem is NP-Hard
Prove 1 : special subset sum \(\le_p\) Load Balancing Problem
special subset sum : \(W=\frac{\sum_{i=1}^n w_i}{2}\) . This is still NPC.
Prove 2 : 3-partition problem \(\le_p\) Load Balancing Problem
3-partition problem :
Given \(3n\) numbers \(a_1,\cdots,a_{3n}\) , partition them into \(n\) groups , with each group \(3\) numbers.
Decide whether we can find a partition , s.t. the sum of each group is the same.
Theorem : 3-partition problem is NPC ( even if \(a_i\) is poly-sized )
Greedy Algorithm 1
Process jobs in arbitrary order one-by-one . Assign the job to the machine with current minimal load.
Analysis : \(\alpha=2\).
Proof :
load of OPT : \(T^*\).
- Observation 1 : \(T^*\ge \max_{i=1}^n t_i\).
- Observation 2 : \(T^*\ge \frac{1}{m}\sum_{i=1}^n t_i\).
Let's prove that \(SOL\le \max_{i=1}^n t_i+\frac{1}{m}\sum_{i=1}^n t_i\) , so \(SOL\le 2T^*\).
Let \(SOL=\sum_{i\in S_j} t_i\) , and \(t_k\) is the last job assigned to machine \(j\) . Therefore , we can prove that before assigning \(t_k\) , the load of machine \(j\) is \(\le \frac{1}{m}\sum_{i=1}^m t_i\) ( since machine \(j\) with current minimal load ) . \(t_k\le \max_{i=1}^n t_i\) . Therefore , \(SOL\le \frac{1}{m}\sum_{i=1}^m t_i +\max_{i=1}^n t_i\).
Worst case :
\(n=m(m-1)+1\) , with \(m(m-1)\) jobs \(t_j=1\) , and \(1\) job \(t_j=m\).
Then \(SOL=2m-1\) , but \(OPT=m\). \(\alpha=\frac{2m-1}{m}\to 2\) .
Greedy Algorithm 2 ( improvement )
Process jobs in decreasing order.
Analysis : \(\alpha=1.5\) ( not tight )
Proof :
Case 1 : \(n\le m\) , \(OPT=SOL\)
Case 2 : \(n>m\) , so \(t_k\le t_{m+1}\le \frac{OPT}{2}\).
\(t_{m+1},t_i\) must be both in one machine for some \(1\le i\le m\).
6.3 \(k\)-Center Problem
Description
Input : a metric graph \(G=(V,E,d)\) , number of centers \(k\).
Def [ metric graph ] : \(d\) satisfies \(\begin{cases}d(u,u)=0&u\in V\\d(u,v)=d(v,u)&u,v\in V\\d(s,t)\le d(s,w)+d(w,t)&s,t,w\in V\end{cases}\).
Output : Choose \(k\) centers \(C=\{c_1,\cdots,c_k\}\subseteq V\). Minimize max cluster radius. \[ d(v,C):=\min_{i=1}^k \{d(v,c_i)\} \] Minimize \(\max_{v\in V}d(v,C)\).
Remark : Applications in ML
unsupervised learning.
\(k\)-means : minimize \(\sum_{v\in V}d(v,C)^2\).
\(k\)-median : minimize \(\sum_{v\in V}d(v,C)\).
Greedy Algorithm with \(\alpha=2\)
Algorithm
Guess optimal radius \(r\) ( at most \(|E|\) possibilities )
Choose an arbitrary vertex \(v\in S\) , \(C\gets C\cup\{v\}\)
Let \(D=\{u\in S:d(u,v)\le 2r\}\) , \(S\gets S\backslash D\)
If \(S\neq \varnothing\) , go to (2)
Finally , if \(|C|>k\) , our guess is too small ( fail )
If \(|C|\le k\) , our guess succeed.
Hopefully , we want if we success at \(r\) , then \(OPT\ge r\) and \(SOL\le 2r\) .
Proof
Key Observation : If \(r\ge OPT\) , then we will definitely success.
Suppose \(C_{OPT}=\{c_1,\cdots,c_{opt}\}\) , and \(b_v=\arg\min_{1\le i\le OPT} d(v,c_i)\) .
In each step , suppose that we choose \(v\) , then \(\forall u\in V,b_u=b_v\) , \(d(u,v)\le d(u,c_{b_v})+d(c_{b_v},v)\le 2r\) . Therefore , \(\{u:b_u=b_v\}\subseteq D_{v}\) .
That is , each step we can remove at least one optimal cluster .
\(\alpha=2\) is the best result
Inapproximability : \(\forall \alpha<2\) , this problem is NP-Hard .
Promise Problem : For a given instance , such that the optimal value is \(\le h\) or \(> \alpha h\) . Decide which case it is.
Claim : Any \(\alpha\)-approximation algorithm can be used to solve Promise Problem.
Approximation answer : \(\le \alpha h\) , then \(OPT\le \alpha h\) , then \(OPT\le h\) , output
true
Approximation answer : $>h $ , then \(OPT>h\) , then \(OPT>\alpha h\) , output
false
THM : Promise \(k\)-center for any \(\alpha<2\) is NPC
Proof : Dominating Set \(\le_p\) Promise \(k\)-center for \(\alpha<2\)
\(G\) for Dominating Set , construct \(G'\) for Promise \(k\)-center for \(\alpha<2\)
\(G'\) : \(E'\) complete graph , \(w(e)=\begin{cases}1&e\in E\\2&e\notin E\end{cases}\)
\((G,k)\in DS\iff\) the answer of \(G'\) is
true
for \((G',k,h=1)\) .