Abstrakt. Vi anser att problemet med att fördela resurser för att tillgodose efterfrågan varierar över tid. Inmatningen anger en efterfrågan för varje tidsrymd. Varje resurs specificeras av en start-tid, sluttid, en tillhörande kostnad och en kapacitet. En genomförbar lösning är en multiuppsättning resurser som vid varje tidpunkt, summan av den kapacitet som erbjuds av resurserna är åtminstone kravet på efterfrågan vid den tidpunkten. Målet är att minimera den totala kostnaden för de resurser som ingår i lösningen. Detta problem uppstår naturligt i många scenarier som personalförvaltning, sensornätverk, datormoln, energihantering och distribuerade datorer. Vi studerar detta problem under den partiella mörkläggningen och noll-ett-inställningen. I det tidigare scenariot, indata innehåller också ett antal k och målet är att välja en lägsta kostnad lösning som uppfyller efterfrågan krav på minst k gångerlots. För detta problem presenterar vi en 16-approximation algoritm; vi visar att det finns "välstrukturerade" nära-optimala lösningar och att en sådan lösning kan hittas i polynom tid via dynamisk programmering. I noll-en-inställningen tillåts en genomförbar lösning att välja högst en kopia av alla resurser. För detta fall presenterar vi en 4- approximationsalgoritm; vår algoritm använder en ny LP-avslappning med flödestäcke ojämlikheter.
I REF anser författarna ett scenario, där tidslotterna har krav och en lösning måste tillgodose efterfrågan på minst k av tidslotterna.
Resource Allocation for Covering Time Varying Demands
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Computer Science']}