Den d-dimensionella vektor packa problem är en välkänd generalisering av den klassiska bin förpackning problem: För en given lista av vektorer i [ 0, 1 ] d, målet är att dela upp listan i det minsta antalet undergrupper, så att i varje undergrupp summan av alla vektorer är som mest en i varje koordinat. För fallet d = 1, utformade Femandez de la Vega och Lueker ( 1981) ett asymptotiskt polynomiskt tidsschema. I denna anmärkning bevisar vi att redan för fallet d = 2, förekomsten av en asymptotisk polynom tid approximation system skulle innebära P = NP. Beviset är mycket enkelt och använder inga nya idéer. @ 1997 Elsevier Science B.V.
För 2-dimensionell paketering av vektorbehållare visade Woeginger REF att det inte finns några APTAS.
There is no asymptotic PTAS for twodimensional vector packing
{'venue': 'Information Processing Letters 64', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}