Search

Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has attracted the attention of many researchers over the last forty years. While the Linear Time-Cost Tradeoff Problem can be solved in polynomial time, its discrete variant is known to be NP-hard. We present the first approximation algorithms for the Discrete Time-Cost Tradeoff Problem. Specifically, given a fixed budget we consider the problem of finding a shortest schedule for a project. We give an approximation algorithm with performance ratio 3/2 for the class of projects where all feasible durations of activities are either 0, 1, or 2. We extend our result by giving approximation algorithms with performance guarantee O(log l), where l is the ratio of the maximum duration of any activity to the minimum nonzero duration of any activity. Finally, we discuss bicriteria approximation algorithms which compute schedules for a given deadline or budget such that both project duration and cost are within a constant factor of the duration and cost of an optimum schedule for the given deadline or budget.

We apply network flow techniques to find good exit selections for evacuees in an emergency evacuation. More precisely, we present two algorithms for computing exit distributions using both classical flows and flows over time which are well known from combinatorial optimization. The performance of these new proposals is compared to a simple shortest path approach and to a best response dynamics approach by using a cellular automaton model.

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of $3.79$ for virtual private network design. This is a considerable improvement of the previously best known $5.55$-approximation result [A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365-372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce the approximation ratio to $3.55$. To the best of our knowledge, this is the first time that a nontrivial result from exact (exponential) algorithms leads to an improved polynomial-time approximation algorithm.

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks $\tau_i=(c_i,p_i)$ on a minimum number of identical machines and to compute offsets $a_i$ for the tasks such that no collision occurs. A task $\tau_i$ releases a job of running time $c_i$ at each time $a_i + k\cdot p_i$, $k\in\setN$ and a collision occurs if two jobs are simultaneously active on the same machine. Our main results are as follows: (i) We show that the minimization problem cannot be approximated within a factor of $n^{1-\epsilon}$ for any $\epsilon>0$. (ii) If the periods are dividing (for each $i,j$ one has $p_i \mid p_j$ or $p_j \mid p_i$), then there exists a 2-approximation for the minimization problem and this result is tight, even asymptotically. (iii) We provide asymptotic approximation schemes in the dividing case if the number of different periods is constant.

We consider the problem of scheduling jobs with release dates on parallel machines so as to minimize average weighted completion time. While constant factor approximation algorithms for many variants have been developed in the last few years, we present the first known polynomial time approximation schemes for several of them. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our PTASs are also efficient. For most variants, the running time for a (1+ε)-approximation on an instance with n jobs and m machines is O(nlog n) for each fixed ε, and for all variants the running time's dependence on n is a fixed polynomial whose degree is independent of ε and m.