j_pmt

• maximal polynomially solvable:
  $ J \vert prec;r_i;n=2;pmtn \vert \sum w_iU_i$ Sotskov (1991) [5]
  $ J \vert prec;r_i;n=2;pmtn \vert \sum w_iT_i$ Sotskov (1991) [5]

  ---

• maximal pseudopolynomially solvable:
  $ J \vert prec;r_i;n=k;pmtn \vert \sum w_iU_i$ Middendorf & Timkovsky (1999) [4]
  $ J \vert prec;r_i;n=k;pmtn \vert \sum w_iT_i$ Middendorf & Timkovsky (1999) [4]

  ---

• minimal NP-hard:
  $ J2 \vert n=3;pmtn \vert C_{max}$ Brucker et al. (1999B) [1]
  $ * $ $ J2 \vert pmtn \vert C_{max}$ Lenstra & Rinnooy Kan (1979) [3]
  $ J2 \vert n=3;pmtn \vert \sum C_i$ Brucker et al. (1999B) [1]
  $ * $ $ J2 \vert pmtn \vert \sum C_i$ Lenstra (-) [2]

  ---

• Bibliography
• About this document ...