Det gemensamma påfyllningsproblemet är en grundläggande modell i supply chain management teori som har tillämpningar inom lagerhantering, logistik och underhåll schemaläggning. I detta problem finns det flera objekt typer, var och en har en given tidsberoende sekvens av krav som måste uppfyllas. För att tillgodose efterfrågan måste order av posttyperna placeras före förfallodagen för varje efterfrågan. Varje gång en ordning av objekttyper placeras, det finns en associerad gemensam installationskostnad beroende på den delmängd av objekttyper som beställts. Denna beställningskostnad kan till exempel bero på maskin-, transport- eller arbetskostnader. Dessutom finns det en kostnad för att hålla lager för efterfrågan som ännu inte har tjänats. Det övergripande målet är att minimera de totala beställningskostnaderna plus lagerhållningskostnader. I detta dokument är kostnaden för en order, även känd som en gemensam installationskostnad, en monotont ökande, submodulär funktion över posttyper. För detta allmänna problem visar vi att ett girigt tillvägagångssätt ger en ungefärlig garanti som är logaritmisk i fråga om antalet krav. Sedan överväger vi tre speciella fall av submodulära funktioner som vi kallar laminar, träd, och kardinalitet fall, som var och en kan modellera verkliga scenarion som tidigare inte har fångats. För vart och ett av dessa fall ger vi en konstant faktor
IRP om trädmått har en konstant approximation REF.
The submodular joint replenishment problem
{'venue': None, 'journal': 'Mathematical Programming', 'mag_field_of_study': ['Mathematics', 'Computer Science']}