优先序约束的排序问题：基于最大匹配的近似算法

张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉

Maximum matching based approximation algorithms for precedence constrained scheduling problems

An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN

Table 1 Complexity and approximability results on precedence constrained scheduling

Problem Complexity Approximation $ P \mid prec \mid C_{\max} $ NP-hard[2] $ 2 - \frac 1m $[2] $ P \mid prec, p_j = 1 \mid C_{\max} $ NP-hard to $ 2 $-approx[8] $ 2 - \frac 2m $[4, 5] $ P \mid prec \mid C_{\max} $, $ m {\geqslant} 4 $ NP-hard $ 2 - \frac 7{3m+1} $[6] $ m {\geqslant} 3 $ NP-hard open[9] $ Pm \mid prec, p_j = 1 \mid C_{\max} $ $ m {\geqslant} 4 $ PTAS open[10] $ m {\geqslant} 4 $ Not APX-hard[11] $ O \mid prec, p_{ij} = 1\mid C_{\max} $ Strongly NP-hard[13, 14] $ 2 - \frac 2m $ ([19] and this paper) $ F \mid prec, p_{ij} = 1\mid C_{\max} $ Strongly NP-hard[13, 14] $ F \mid spine, p_{ij} = 1\mid C_{\max} $ NP-hard open $ 2 - \frac 2m $ (this paper) $ O/F \mid intree/outtree, p_{ij} = 1\mid C_{\max} $ P[16, 17] $ O/F \mid intree, p_{ij} = 1\mid L_{\max} $ P[15, 16] $ O/F \mid outtree, p_{ij} = 1\mid L_{\max} $ Strongly NP-hard[14, 18] $ Om/Fm \mid prec, p_{ij} = 1 \mid C_{\max} $, $ m {\geqslant} 3 $ NP-hard open $ O2/F2 \mid prec, p_{ij} = 1 \mid L_{\max} $ P[15, 16]