På grund av sin uppenbara praktiska relevans har Time-Cost Tradeoff-problemet uppmärksammats av många forskare under de senaste trettio åren. I detta sammanhang överväger vi projekt som ges av en uppsättning enskilda verksamheter och företrädesbegränsningar för dessa verksamheter. Varaktigheten för varje aktivitet varierar. Ju kortare den valda varaktigheten är, desto högre är dock kostnaden för att utföra verksamheten. Detta definierar den korrekta tid-kostnads-avvägningen: korta projektlängder motsvarar höga kostnader och vice versa. Om kostnaden för en enda aktivitet beror linjärt på den valda varaktigheten, kan Time-Cost Tradeoff problemet exakt lösas i polynom tid. Dess diskreta variant är dock känd för att vara NPhard. Därför har det tidigare funnits flera heuristiska försök att hitta "bra" algoritmer för att lösa detta problem. I detta papper presenterar vi de första polynom-tids approximation algoritmer för Discrete Time-Cost Tradeoff Problem med konstant prestanda garanti på olika speciella klasser av instanser. Vi anser särskilt att problemet är att hitta en optimal tidsplan för ett projekt med en viss budget som inte får överutnyttjas. Vi ger en polynom tid approximation algoritm med en prestandakvot på $ för projekt med alternativ O/l eller O/2 för varaktigheten av varje aktivitet. Dessutom kan vi visa att detta är den bästa approximationen som kan hittas, om inte P = NP. Slutligen, vi typ av generalisera vårt resultat till godtyckliga projekt genom att ge en approximationsalgoritm med en prestandagaranti 3 log2e + 5. Här är e förhållandet mellan den maximala tillåtna varaktigheten för någon aktivitet och den minsta tillåtna icke-noll varaktigheten för någon aktivitet.
För detta problem föreslog Skutella Ref den första approximationsalgoritmen under budgetbegränsningar som uppnår en approximationsgrad på O (log r ), där r är förhållandet mellan den maximala varaktigheten för en verksamhet och den minsta.
Approximation algorithms for the discrete time-cost tradeoff problem
{'venue': "SODA '97", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}