Sensitivity analysis for knapsack problems : another negative result

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (Scopus)

    Abstract

    We answer a question of Blair [Discrete Appl. Math. 81 (1998) 133–139] on the computational complexity of a problem related to the so-called adjacent knapsack problems. We prove that this problem is DP-hard; hence, the problem is at least as difficult as all problems in NP and at least as difficult as all problems in coNP.
    Original languageEnglish
    Pages (from-to)247-251
    JournalDiscrete Applied Mathematics
    Volume92
    Issue number2-3
    DOIs
    Publication statusPublished - 1999

    Fingerprint

    Dive into the research topics of 'Sensitivity analysis for knapsack problems : another negative result'. Together they form a unique fingerprint.

    Cite this