Abstrakt. I detta dokument behandlar vi problemet med Wafer-till-Wafer-integration. En wafer är en p-dimensionell binär vektor. Inmatningen av detta problem beskrivs av m disjokes uppsättningar (kallas "partier"), där varje uppsättning innehåller n plattor. Utgången av problemet är en uppsättning n separata stackar, där en stack är en uppsättning m plattor (en wafer från varje parti). Till varje stack associerar vi en p-dimensionell binär vektor som motsvarar bitvis OCH drift av plattorna i stacken. Målet är att maximera det totala antalet "1" i n stackarna. Vi tillhandahåller O(m 1- ) och O(p 1- ) icke- approximabilitet resultat även för n = 2, samt en p r - approximation algoritm för alla konstant r. Slutligen visar vi att problemet är FPT när parameteriserad av p, och vi använder denna FPT algoritm för att förbättra körtiden för p r - approximation algoritm.
Den viktigaste relaterade artikeln är REF där det bevisas att max 1-BMVA inte har någon O(p 1- på ) eller O(m 1- på )- approximation för någon  på > 0 om inte P = NP (även när n = 2), men medger en p c - approximation algoritm för någon konstant c  på N, och är FPT när parameteriserad av p (som också innehar för BMVA).
On the Complexity of Wafer-to-Wafer Integration
{'venue': 'CIAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}