Abstrakt. I denna uppsats studerar vi det stokastiska obundna min-knapsack-problemet (Min-SUKP). Den vanliga obundna min-knapsack problemet anger att: Det finns n typer av objekt, och det finns ett oändligt antal objekt av varje typ. Posterna av samma typ har samma kostnad och vikt. Vi vill välja en uppsättning objekt så att den totala vikten är minst W och den totala kostnaden minimeras. Min-SUKP generaliserar den vanliga obundna min-knapsack problemet till den stokastiska inställningen, där vikten av varje objekt är en slumpmässig variabel efter en känd fördelning och objekt av samma typ följer samma viktfördelning. I Min-SUKP kan olika typer av produkter ha olika kostnads- och viktfördelning. I detta dokument tillhandahåller vi en FPTAS för Min-SUKP, dvs. det ungefärliga värdet våra algoritmberäkningar är som mest (1 +  på) gånger den optimala, och vår algoritm körs i poly(1/ på, n, log W ) tid.
Den obundna versionen av Stoch-Knapsack Cover (varje artikel har oändligt många kopior) studerades av REF och de tillhandahåller en FPTAS för detta problem.
An FPTAS for Stochastic Unbounded Min-Knapsack Problem
{'venue': 'In Chen Y., Deng X., Lu M. (eds) Frontiers in Algorithmics. FAW 2019. Lecture Notes in Computer Science, vol 11458. Springer, Cham', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}