Simple but efficient approaches for the collapsing knapsack problem

U. Pferschy, D. Pisinger, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    17 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    The collapsing knapsack problem is a generalization of the ordinary knapsack problem, where the knapsack capacity is a non-increasing function of the number of items included. Whereas previous papers on the topic have applied quite involved techniques, the current paper presents and analyzes two rather simple approaches: One approach that is based on the reduction to a standard knapsack problem, and another approach that is based on a simple dynamic programming recursion. Both algorithms have pseudo-polynomial solution times, guaranteeing reasonable solution times for moderate coefficient sizes. Computational experiments are provided to expose the efficiency of the two approaches compared to previous algorithms.
    Original languageEnglish
    Pages (from-to)271-280
    JournalDiscrete Applied Mathematics
    Volume77
    Issue number3
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'Simple but efficient approaches for the collapsing knapsack problem'. Together they form a unique fingerprint.

    Cite this