I den d-dimensionella (vektor) knapsack problem ges är en uppsättning objekt, var och en med en d-dimensionell storlek vektor och en vinst, och en d-dimensionell bin. Målet är att välja en delmängd av objekten med maximal total vinst så att summan av alla vektorer begränsas av bin kapacitet i varje dimension. Det är väl känt att om inte P = N P, Det finns ingen helt polynom tid approximation system för d-dimensionell knapsack, redan för d = 2. Det mest kända resultatet är ett polynom tid approximation system (PTAS) på grund av Frieze och Clarke (European J. of Operational Research, 100-109, 1984 ) I detta dokument vi lösa denna fråga genom att visa att det inte finns någon EPTAS för ddimensionell knapsack, redan för d = 2, om inte W [1] = F P T. Dessutom visar vi att om inte alla problem i SNP är lösliga i sub-exponentiell tid, det finns ingen approximation system för två-dimensionell knapsack vars körtid är f (1/ε) och I på grund av alla funktioner f. Tillsammans, de två resultaten tyder på att en betydande förbättring över driftstiden för systemet Frieze och Clarke är osannolikt att existera.
I själva verket finns det inget effektivt system för approximering av polynomtid (EPTAS) för 2-KP om inte W[1] = FPT (se REF ).
There is no EPTAS for two-dimensional knapsack
{'venue': 'Inf. Process. Lett', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}