A note on the depth function of combinatorial optimization problems

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    In a recent paper [Discrete Appl. Math. 43 (1993) 115–129], Kern formulates two conjectures on the relationship between the computational complexity of computing the depth function of a discrete optimization problem and the computational complexity of solving this optimization problem to optimality. In this note (that might be considered to be a kind of erratum to Kern's paper), we exhibit simple counterexamples to both conjectures under the assumption P¿NP.
    Original languageEnglish
    Pages (from-to)325-328
    JournalDiscrete Applied Mathematics
    Volume108
    Issue number3
    DOIs
    Publication statusPublished - 2001

    Fingerprint Dive into the research topics of 'A note on the depth function of combinatorial optimization problems'. Together they form a unique fingerprint.

    Cite this