Günter Rote and André Schulz:

Threshold arrangements and the knapsack problem

Applied Mathematics Letters 19 (2006), 108-112. doi:10.1016/j.aml.2005.03.010


We show that a combinatorial question which has been studied in connection with lower bounds for the knapsack problem by Brimkov and Dantchev (Applied Mathematics Letters, 2002) is related to threshold graphs, threshold arrangements, and other well-studied combinatorial objects, and we correct an error in the analysis given in that paper.

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: January 8, 2008.