Abstrakt. I detta papper, vi tar itu med online minimization knapsack problem, dvs., objekten ges en efter en över tid och målet är att minimera den totala kostnaden för objekt som täcker en knapsack. Vi studerar den borttagbara modellen, där det är tillåtet att ta bort gamla objekt från ryggsäcken för att acceptera ett nytt objekt. Vi får följande resultat. (i) Vi föreslår en 8-konkurrenskraftig deterministisk och minneslös algoritm för problemet, som kontrasterar mot resultatet för online maximization knapsack problem att ingen online-algoritm har ett begränsat konkurrensförhållande [8]. (ii) Vi föreslår en 2e-kompetitiv randomiserad algoritm för problemet. (iii) Vi härleder en lägre gräns 2 för deterministiska algoritmer för problemet. (iv) Vi föreslår en 1.618-konkurrensutsatt deterministisk algoritm för det fall där varje post har sin storlek som motsvarar dess kostnad, och visar att detta är bästa möjliga.
Han och Makino REF anses vara en online-version av min-knapsack, dvs objekten ges en efter en över tid.