Strip packning är ett klassiskt förpackningsproblem, där målet är att packa en uppsättning rektangulära objekt i en remsa med en given bredd, samtidigt minimera den totala höjden på förpackningen. Problemet har flera tillämpningar, till exempel i schemaläggning och lagerskärning, och har studerats i stor utsträckning. När objektens dimensioner tillåts vara exponentiella i den totala ingångsstorleken, är det känt att problemet inte kan approximeras inom en faktor som är bättre än 3/2, om inte P = NP. Det fanns dock ingen motsvarande lägre gräns för polynombundet ingångsdata. I själva verket har Nadiradze och Wiese [SODA 2016] nyligen föreslagit en (1.4 + ε ) - approximation algoritm för denna variant, vilket visar att band förpackning med polynomiskt bundna data kan approximeras bättre än när exponentiellt stora värden tillåts i inmatningen. Deras resultat har därefter förbättrats till en (4/3 + ε ) approximation av två oberoende forskargrupper [FSTTCS 2016, WALCOM 2017. Detta väcker en fråga om strip packning med polynomiskt avgränsade indata medger en kvasi-polynom tid approximation system, som är fallet för relaterade tvådimensionella förpackningsproblem som maximal oberoende uppsättning av rektanglar eller tvådimensionell knapsack. I den här artikeln besvarar vi denna fråga negativt genom att bevisa att det är NP-hårdt att approximera strip packning inom en faktor som är bättre än 12/11, även när det är begränsat till polynomiskt begränsade indata. I synnerhet visar detta att problemet med strip packning tillåter inget kvasi-polynom tid approximation system, om inte NP  en DTIME( 2 polylog( n) ).
Adamaszek m.fl. REF visade att det inte finns någon PPT ( 12 11 – ε) - approximationsalgoritm för Strip Packing om inte N P  på DT IM E(2 polylog(n) ).
Hardness of Approximation for Strip Packing
{'venue': 'TOCT', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}