Output details

Fast approximation schemes for Boolean programming and scheduling problems related to positive convex Half-Product

This research has been undertaken within the project EP/018441/1 “Quadratic & Linear Knapsack Problems with Scheduling Applications” funded by the EPSRC (2011-2013). It complements earlier results obtained by the authors that are summarised in the invited survey paper (4OR, 2012, 10, 111-161). A practically relevant form of the half-product problem, with and without a knapsack constraint, has been identified and the fastest possible FPTAS has been developed for its approximate solution. The content of this paper was a major part of the invited keynote presentation that Prof Strusevich made at the 55th Conference of the OR Society (Exeter, 2013).