I detta dokument behandlas två varianter av flera Knapsack-problem. Den första är problemet med flera Knapsack med tilldelningsbegränsningar och kapacitetsbegränsningar (MK-AR-CC). I MK-AR-CC(k) (där k är ett positivt heltal) är en undergrupp av knapsacks associerad med varje objekt och objektet kan packas i endast de knapsacks (Tillsättningsbegränsningar). Dessutom är storleken på varje knapsack minst k gånger den största posten som kan tilldelas knapsacken (Kapacitetsbegränsningar). MK-AR-CC(k) är NP-hård för varje konstant k. I detta papper ger vi en polynom-tid " 1 + 2 k+1 + " -tillnärmningsalgoritm för MK-AR-CC(k), och ger en lägre gräns på approximationen förhållandet av vår algoritm genom att visa en integrality gap av `1 + 1 k − 'f eller IP-formuleringen vi använder i vår algoritm, där är en godtycklig liten positiv konstant. Det andra problemet är den Splittable Multiple Knapsack Problem med Uppdragsbegränsningar (S-MK-AR), där storleken på objekt kan överstiga kapaciteten för Knapsacks och objekt kan delas och packas i flera Knapsacks. Vi visar att approximeringen av S-MK-AR med förhållandet n 1— är NP-hård även när alla objekt har samma vinst, där n är antalet poster och är en godtycklig positiv konstant.
Det närmaste problemet är problemet med flera 0-1 Knapsack med uppdragsbegränsningar och kapacitetsbegränsningar (MK-AR-CC) REF, där flera knapsacks är oberoende.
Approximability of Two Variants of Multiple Knapsack Problems
{'venue': 'CIAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}