MP15 M AXIMUM I NTEGER K -C HOICE K NAPSACK

     
• I NSTANCE : Nonnegative integer -matrices , nonnegative integer .
• S OLUTION : Nonnegative integer vector , function such that .
• M EASURE : .

• Good News: Admits an FPTAS [ 63 ].
• Comment: The corresponding minimization problem, where also admits an FPTAS as well as the variation in which there does not need to be a chosen element for each i [ 129 ].
• Garey and Johnson: Similar to MP11