Simple but efficient approaches for the collapsing knapsack problem

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    17 Citaties (SciVal)
    1 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)271-280
    TijdschriftDiscrete Applied Mathematics
    Nummer van het tijdschrift3
    StatusGepubliceerd - 1997


    Duik in de onderzoeksthema's van 'Simple but efficient approaches for the collapsing knapsack problem'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit