A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

Hans Kellerer and Vitaly A. Strusevich
Theoretical Computer Science
Volume 369, Issues 1-3, 15 December 2006, Pages 230-238
http://dx.doi.org/10.1016/j.tcs.2006.08.030

スケジューリングについて．
1機械で，release dateはなし．このとき，遅れ (tardiness) の重み付き総和を最小化したい．
特に，due dateが全てのjobに対して同一である場合を扱っている．
この問題に対してはFathi and Nuttle (1990) の多項式時間2近似アルゴリズムがある．
少し一般化してdue dateの種類が定数の場合，Kolliopoulos and Steiner (2006) は擬多項式時間の近似スキームを提案している．
またdue dateに制限がない場合，Cheng, Ng, Yuan, and Liu (2005) は多項式時間n-1近似アルゴリズムを提案している．(nはjobの数．)

この論文は，due dateが同一の場合に対して，FPTAS (fully polynomial-time approximation scheme) を与えている．提案アルゴリズムの中ではFathi and Nuttleによる上述のアルゴリズムから得られる値を下界として用い，新たに開発した動的計画厳密アルゴリズムを丸めたインスタンスに適用して解を得ている．

アルゴリズムはFPTASであるが，計算量が弱多項式であるため，強多項式のFPTASができるかどうかが未解決で残されている．また，due dateの種類が定数の場合のFPTASも未解決．