TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1997

COGA 5-Wheel


zur Navigation

Preprints 1997

Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem
Zitatschlüssel Report-514-1996
Autor Martin Skutella
Jahr 1996
Nummer 514
Notiz To appear in Mathematics of Operations Research.<P> An extended abstract appeared in Michael Saks et al., editors, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97). Society of Industrial and Applied Mathematics (1997), 501-508.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has achieved the attention of many researchers over the last thirty years. Within this context, we consider projects given by a set of single activities and precedence constraints on these activities. The duration of each activity is variable. However, the shorter the chosen duration is, the higher is the cost caused by executing the activity. This defines the proper \emphtime-cost tradeoff: short project durations correspond to high cost and vice versa. If the cost of a single activity depends linearly on the chosen duration, the Time-Cost Tradeoff Problem can exactly be solved in polynomial time. However, its discrete variant is known to be $\NP$–hard. Hence, in the past there have been several heuristic attempts to find ``good'' algorithms to solve this problem. In this paper we present the first polynomial-time approximation algorithms for the Discrete Time-Cost Tradeoff Problem with constant performance guarantee on various special classes of instances. Specifically, we consider the problem of finding an optimal schedule for a project with a given budget that must not be overspent. We give a polynomial time approximation algorithm with a performance ratio of $\frac32$ for projects with alternatives $0/1$ or $0/2$ for the duration of each activity. Moreover, we can show that this is the best approximation that can be found, unless $\P=\NP$. Finally, we kind of generalize our result to arbitrary projects by giving an approximation algorithm with a performance guarantee $\frac32łog_2\ell+\frac72$. Here, ℓ is the ratio of the maximum difference between allowed durations of any activity to the minimum difference.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe