There is no asymptotic PTAS for two-dimensional vector packing

    Research output: Contribution to journalArticleAcademicpeer-review

    80 Citations (Scopus)

    Abstract

    The d-dimensional vector packing problem is a well-known generalization of the classical bin packing problem: For a given list of vectors in [0, 1]d, the goal is to partition the list into the minimum number of subsets, such that in every subset the sum of all vectors is at most one in every coordinate. For the case d = 1, Fernandez de la Vega and Lueker (1981) designed an asymptotic polynomial time approximation scheme. In this note we prove that already for the case d = 2, the existence of an asymptotic polynomial time approximation scheme would imply P = NP. The proof is very simple and uses no new ideas.
    Original languageEnglish
    Pages (from-to)293-297
    JournalInformation Processing Letters
    Volume64
    Issue number6
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'There is no asymptotic PTAS for two-dimensional vector packing'. Together they form a unique fingerprint.

    Cite this