Många system måste upprätthållas medan de underliggande begränsningarna, kostnaderna och/eller vinsterna förändras över tiden. Även om tillståndet i ett system kan utvecklas under tiden, uppstår en icke försumbar övergångskostnad för övergången från en stat till en annan. För att modellera sådana situationer, Gupta et al. (ICAP 2014) och Eisenstat m.fl. (ICAP 2014) införde en flerstegsmodell där inmatningen är en sekvens av instanser (ett för varje tidssteg), och målet är att hitta en sekvens av lösningar (en för varje tidssteg) som är både (i) nära optimal för varje tidssteg och (ii) så stabil som möjligt. Vi fokuserar på flerstegsversionen av Knapsack problem där vi ges en tidshorisont t = 1, 2,..., T, och en sekvens av Knapsack fall I 1, I 2,. .., I T, en för varje steg, definieras på en uppsättning n objekt. I varje gång steg t måste vi välja en genomförbar knapsack S t av I t, vilket ger en knapsack vinst. För att mäta stabiliteten / likheten av två på varandra följande lösningar S t och S t+1, identifierar vi de objekt för vilka beslutet, att plockas eller inte, förblir densamma i S t och S t+1, vilket ger en övergångsvinst. Vi uppmanas att producera en sekvens av lösningar S 1, S 2,. .., S T så att den totala knapsack vinst plus den totala övergångsvinst maximeras. Vi föreslår en PTAS för flerstegs Knapsack-problemet. Detta är det första approximationsschemat för ett kombinatoriellt optimeringsproblem i den anses flerstegsinställningen, och dess existens kontrasterar mot de otillåtliga resultaten för andra kombinatoriska optimeringsproblem som till och med kan lösas med polynom i det statiska fallet (t.ex. multistage Spanning Tree, eller multistage Bipartite Perfect Matching). Sedan bevisar vi att det inte finns någon FPTAS för problemet även i fallet där T = 2, om inte P = N P. Dessutom ger vi en pseudopolynom tid algoritm för fallet där antalet steg begränsas av en fast konstant och vi visar att annars problemet förblir NP-hård även i fallet där alla vikter, vinster och kapaciteter är 0 eller 1.  ACM Subject Classification I en klassisk kombinatorisk optimering problem, med tanke på en instans av problemet vi söker en genomförbar lösning optimera den objektiva funktionen. I många system kan dock inmatningen förändras över tiden och lösningen måste anpassas till inmatningsändringarna. Det är då nödvändigt att fastställa en avvägning mellan hur optimala lösningarna är för varje steg i tiden och stabiliteten/likheten hos på varandra följande lösningar. Detta är viktigt eftersom det i många tillämpningar finns en betydande övergångskostnad för att ändra (delar av) en lösning. Nyligen,
På senare tid har en flerstegs variant av Knapsack-problemet undersökts i REF.
Multistage Knapsack
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}