 FG Kombinatorische Optimierung und Graphenalgorithmen1997 # Preprints 1997

Zitatschlüssel Report-514-1996 Martin Skutella 1996 514 To appear in Mathematics of Operations Research.

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. Technische Universität Berlin, Institut für Mathematik 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. Preprint