Vi anser att en speciell klass av axiella flerdimensionella tilldelningsproblem som kallas flerdimensionell vektortilldelning (MVA) problem. Ett exempel på MVA-problemet definieras av m-separationsenheter, som var och en innehåller samma antal n p-dimensionella vektorer med icke-negativa integrerade komponenter, och en kostnadsfunktion som definieras på vektorer. Kostnaden för en m-tuple av vektorer definieras som kostnaden för deras komponentvisa maximum. Problemet är nu att dela upp m-uppsättningarna vektorer i n m-tuples så att inga två vektorer från samma uppsättning är i samma m-tuple och så att summan av kostnaderna för m-tuples minimeras. Huvudmotivationen kommer från ett problem med avkastningsoptimering inom halvledartillverkning. Vi betraktar en viss klass av polynom-tidsheuristik för MVA, nämligen sekventiell heuristik, och vi studerar deras approximationsförhållande. I synnerhet visar vi att när kostnadsfunktionen är monoton och subadditiv har sekventiell heuristik ett finit approximationsförhållande för varje fast m. Dessutom fastställer vi mindre approximationsförhållanden när kostnadsfunktionen är submodulär och, för en specifik sekventiell heuristisk, när kostnadsfunktionen är additiv. Vi ger exempel för att illustrera tätheten i vår analys. Dessutom visar vi att MVA-problemet är APX-hård även för fallet m = 3 och för binära ingångsvektorer. Slutligen visar vi att problemet kan lösas i polynom tid i specialfallet av binära vektorer med fast dimension p.
Den mer komplexa minskningen av REF visar att min 0 är APX-hård även för m = 3, och därmed är mycket osannolikt att erkänna en PTAS.
Multi-dimensional vector assignment problems
{'venue': 'Discret. Optim.', 'journal': 'Discret. Optim.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}