Search

The Moore-Hodgson Algorithm minimizes the number of late jobs on a single machine. That is, it finds an optimal schedule for the classical problem $1~|\;|~\sum{U_j}$. Several proofs of the correctness of this algorithm have been published. We present a new short proof., Comment: 3 pages

23rd EURO Working Group on Transportation Meeting, EWGT 2020, online, 16 Sep 2020 - 18 Sep 2020; Transportation research procedia 52, 123-130 (2021). doi:10.1016/j.trpro.2021.01.014 special issue: "23rd EURO Working Group on Transportation Meeting, EWGT 2020, 16-18 September 2020, Paphos, Cyprus / Edited by Stelios Timotheou, Christos G. Panayiotou", Published by Elsevier, Amsterdam [u.a.]

International audience; As parallel processing became ubiquitous in modern computing systems, parallel task models have been proposed to describe the structure of parallel applications. The workflow scheduling problem has been studied extensively over past years, focusing on multiprocessor systems and distributed environments (e.g. grids, clusters). In workflow scheduling, applications are modeled as directed acyclic graphs (DAGs). DAGs have also been introduced in the real-time scheduling community to model the execution of multi-threaded programs on a multi-core architecture. The DAG model assumes, in most cases, a fixed DAG structure capturing only straight-line code. Only recently, more general models have been proposed. In particular, the conditional DAG model allows the presence of control structures such as conditional (if-then-else) constructs. While first algorithmic results have been presented for the conditional DAG model, the complexity of schedulability analysis remains wide open. We perform a thorough analysis on the worst-case makespan (latest completion time) of a conditional DAG task under list scheduling (a.k.a. fixed-priority scheduling). We show several hardness results concerning the complexity of the optimization problem on multiple processors, even if the conditional DAG has a well-nested structure. For general conditional DAG tasks, the problem is intractable even on a single processor. Complementing these negative results, we show that certain practice-relevant DAG structures are very well tractable.

Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks.

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.

Scheduling a set of n jobs on m identical parallel machines so as to minimize the makespan or maximize the minimum machine load are two of the most important and fundamental scheduling problems studied in the literature. We consider the general online scenario where jobs are consecutively added to and/or deleted from an instance. The goal is to maintain a near-optimal assignment of the current set of jobs to the m machines. This goal is essentially doomed to failure unless, upon arrival or departure of a job, we allow reassigning some other jobs. Considering that the reassignment of a job induces a cost proportional to its size, the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs. The value r is called the reassignment factor of the solution and it is a measure of our willingness to adapt the solution over time. Our main result is that, for any ε > 0, it is possible to achieve (1 + ε)-competitive solutions with constant reassignment factor r(ε). For the minimum makespan problem this is the first improvement on the (2 + ε)-competitive algorithm by Andrews et al. (1999) [Andrews M, Goemans M, Zhang L (1999) Improved bounds for on-line load balancing. Algorithmica 23(4):278–301]. Crucial to our algorithm is a new insight into the structure of robust, almost optimal schedules.

We report on the solution of a difficult optimization problem which arises in avionics industry. When constructing the on-board controlling-network of an airplane, the engineers need to solve a computationally highly complex problem. The goal is to assign periodic tasks to the processors on the plane and define a schedule for each processor. Current state-of-the-art approaches to tackle the problem are by far not powerful enough to solve instances of real-world size. With the help of the powerful algorithm engineering paradigm we analyzed the mathematical properties of the scheduling problem and designed sophisticated software based on the structural insights. We were able to design a model that outperformed current state-of-the-art approaches by several orders of magnitude. In particular, we could solve industrial size real-world instances to optimality. Our methods lead, for the first time, to an industrial strength tool to schedule aircraft sized instances.

Robotic welding cells are at the core of many complex production systems, especially in automotive industry. In these cells, a certain number of robots perform spot welding tasks on a workpiece. The configuration of the cells can have a huge impact on the production rate. The smaller the cycle time is, the higher the production is. In this paper, we present a complete algorithm that automatically configures the welding cell such that the given cycle time of the production process is kept. This algorithm assigns tasks to the different robots, decides in which order the tasks are executed and computes the fastest collision-free trajectory of the robots between two consecutive tasks.

We present a e/(e1)-approximation algorithm for the nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on a single machine subject to release dates and precedence constraints. The previously best known approximation algorithm dates back to 1997; its performance guarantee can be made arbitrarily close to the Euler constant e (Schulz and Skutella, 1997).

Multi-commodity flows over time exhibit the non-intuitive property that letting flow wait can allow us to send flow faster overall. Fleischer and Skutella (IPCO~2002) show that the speed-up through storage is at most a factor of~$2$, and that there are instances where the speed-up is as large as a factor of~$4/3$. We close this gap by presenting a family of instances for which the speed-up factor through storage converges to~$2$.

We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community. We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is the so-called deterministic queuing model that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.

Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.

Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. We concentrate on maximum flow problems and introduce a novel robust optimization model which, compared to known models from the literature, features several advantageous properties: (i) We consider a general class of path-based flow problems which can be used to model a large variety of network routing problems (and other packing problems). (ii) We aim at solutions that are robust against targeted attacks by a potent adversary who may attack any flow path of his choice on any edge of the network. (iii) In contrast to previous robust maximum flow models, for which no efficient algorithms are known, optimal robust flows for the most important basic variants of our model can be found in polynomial time. We also consider generalizations where the flow player can spend a budget to protect the network against the interdictor. Here, we show that the problem can be solved efficiently when the interdiction costs are determined by the flow player from scratch. However, the problem becomes hard to approximate when the flow player has to improve an initial protection infrastructure.

Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g. the Internet) and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks.While the ‘maximum s–t-flow over time’ problem can be solved efficiently and ‘min-cost flows over time’ are known to be NP-hard, the complexity of (fractional) ‘multicommodity flows over time’ has been open for many years. We prove that this problem is NP-hard, even for series–parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.

We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem UFLP and seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. We say that a sequence has a competitive ratio of k, if the cost of serving the first i¾? customers in the sequence is at most k times the optimal solution for serving any i¾? customers for all possible values of i¾?. We provide an incremental framework that computes a sequence with a competitive ratio of at most eight and a worst-case instance that provides a lower bound of three for any incremental sequence. We also present the results of our computational experiments carried out on a set of benchmark instances for the UFLP. The problem has applications in multistage network planning. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 654, 306-311 2015

We consider the optimization problem of scheduling a given set of jobs on unrelated parallel machines with total weighted completion time objective. This is a classical scheduling problem known to be NP-hard since the 1970s. We give a new and simplified version of the currently best-known approximation algorithm, which dates back to 1998. It achieves performance ratio 3 / 2, and is based on an optimal solution to a convex quadratic program.

Are you looking for new lectures for your course on algorithms, combinatorial optimization, or algorithmic game theory? Maybe you need a convenient source of relevant, current topics for a graduate student or advanced undergraduate student seminar? Or perhaps you just want an enjoyable look at some beautiful mathematical and algorithmic results, ideas, proofs, concepts, and techniques in discrete mathematics and theoretical computer science?Gems of Combinatorial Optimization and Graph Algorithms is a handpicked collection of up-to-date articles, carefully prepared by a select group of international experts, who have contributed some of their most mathematically or algorithmically elegant ideas. Topics include longest tours and Steiner trees in geometric spaces, cartograms, resource buying games, congestion games, selfish routing, revenue equivalence and shortest paths, scheduling, linear structures in graphs, contraction hierarchies, budgeted matching problems, and motifs in networks.This volume is aimed at readers with some familiarity of combinatorial optimization, and appeals to researchers, graduate students, and advanced undergraduate students alike.

Flows over time are used to model many real-world logistic and routing problems. The networks underlying such problems-streets, tracks, etc.-are inherently undirected and directions are only imposed on them to reduce the danger of colliding vehicles and similar problems. Thus, the question arises, what influence the orientation of the network has on the network flow over time problem that is being solved on the oriented network. In the literature, this is also referred to as the contraflow or lane reversal problem. We introduce and analyze the price of orientation: How much flow is lost in any orientation of the network if the time horizon remains fixed? We prove that there is always an orientation where we can still send one-third of the flow and this bound is tight. For the special case of networks with a single source or sink, this fraction is half, which is again tight. We present more results of similar flavor and also show nonapproximability results for finding the best orientation for single and multicommodity maximum flows over time. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 663, 196-209 2015

We propose to classify the power of algorithms by the complexity of the problems that they can be used to solve. Instead of restricting to the problem a particular algorithm was designed to solve explicitly, however, we include problems that, with polynomial overhead, can be solved 'implicitly' during the algorithm's execution. For example, we allow to solve a decision problem by suitably transforming the input, executing the algorithm, and observing whether a specific bit in its internal configuration ever switches during the execution. We show that the Simplex Method, the Network Simplex Method (both with Dantzig's original pivot rule), and the Successive Shortest Path Algorithm are NP-mighty, that is, each of these algorithms can be used to solve any problem in NP. This result casts a more favorable light on these algorithms' exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm's execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.

Since the early days of combinatorial optimization, algorithms and techniques from the closely related area of mathematical programming have played a pivotal role in solving combinatorial optimization problems. This holds both for ‘easy’ problems that can be solved efficiently in polynomial time, such as, e. g., the weighted matching problem [3], as well as for NP-hard problems whose solution might take exponential time in the worst case, such as, e. g., the traveling salesperson problem [1].

In welding cells a certain number of robots perform spot welding tasks on a workpiece. The tours of the welding robots are planned in such a way that all weld points on the component are visited and processed within the cycle time of the production line. During this operation, the robot arms must not collide with each other and safety clearances have to be kept. On the basis of these specifications, we concentrate on the Discrete Optimization aspects of the stated problem. This leads to a Vehicle Routing based problem with additional scheduling and timing aspects induced by the necessary collision avoidance. This problem can then be solved as an Integer Linear Program by Column Generation techniques. In this context, we adapt the Resource Constrained Shortest Path Problem, so that it can be used to solve the pricing problem with collision avoidance. Using this approach, we can solve generated test instances based on real world welding cells of reasonable size.

Evacuation, the process of moving people out of potentially dangerous areas, is a key response to many threats. Planning such an evacuation is therefore important, especially in large-scale emergencies, where routing becomes non-trivial. This paper deals with the optimization and simulation of the evacuation process. We draw our data from the study of the city of Padang in Indonesia, with its high threat of tsunami waves.

We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(log n/ log log n) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee. © 2010 Springer-Verlag.

We report on the solution of a real-time scheduling problem that arises in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of machines and offsets of the tasks have to be computed. The tasks emit jobs periodically starting at their offset and then need to be executed on the machines without any delay. Also, further constraints in terms of memory usage and redundancy requirements have to be met. Approaches based on standard integer programming formulations fail to solve our real-world instances. By exploiting structural insights of the problem we obtain an IP-formulation and primal heuristics that together solve the real-world instances to optimality and outperform text-book approaches by several orders of magnitude. Our methods lead, for the first time, to an industry strength tool to optimally schedule aircraft sized problems.

Routing of packets is one of the most fundamental tasks in a network. Limited bandwith requires that some packets cannot move to their destination directly but need to wait in intermediate nodes on their path or take detours. It is desirable to find schedules that ensure fast delivery of the packets, in particular for time critial applications. In this paper we investigate the packet routing problem theoretically. We prove that the problem cannot be approximated with a factor of 6/5-ε for all ε>0 unless P=NP. We show that restricting the graph topology to planar graphs or trees still does not allow a PTAS. For trees we give 2-approximation algorithms for the directed and the undirected case. If the lengths of the paths of the packets are pairwise different, we can compute a schedule of length D on directed trees. Finally, we show that it is NP-hard to approximate the packet routing problem with an absolute error of k for any k>=0.

We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community. We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is the so-called deterministic queuing model that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.

The packet routing problem, i.e., the problem to send a given set of unit-size packets through a network on time, belongs to one of the most fundamental routing problems with important practical applications, e.g., in traffic routing, parallel computing, and the design of communication protocols. The problem involves critical routing and scheduling decisions. One has to determine a suitable (short) origindestination path for each packet and resolve occurring conflicts between packets whose paths have an edge in common. The overall aim is to find a path for each packet and a routing schedule with minimum makespan. A significant topology for practical applications are grid graphs. In this paper, we therefore investigate the packet routing problem under the restriction that the underlying graph is a grid. We establish approximation algorithms and complexity results for the general problem on grids, and under various constraints on the start and destination vertices or on the paths of the packets.

Exchanging messages between nodes of a network (e.g., embedded computers) is a fundamental issue in real-time systems involving critical routing and scheduling decisions. In order for messages to meet their deadlines, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. With this paper we contribute to the theoretic foundations of real-time systems. On the one hand, we provide efficient routing strategies yielding origin-destination paths of bounded dilation and congestion. In particular, we can give good a priori guarantees on the time required to send a given set of messages which, under certain reasonable conditions, implies that all messages can be scheduled to reach their destination on time. Finally, for message routing along a directed path (which is already NP-hard), we identify a natural class of instances for which a simple scheduling heuristic yields provably optimal solutions.

Scheduling jobs on unrelated parallel machines so as to minimize the makespan is one of the basic, well-studied problems in the area of machine scheduling. In the first part of the paper we prove that the power of preemption, i.e., the ratio between the makespan of an optimal nonpreemptive and an optimal preemptive schedule, is exactly 4. This result is a definite answer to an important basic open problem in scheduling. The proof of the lower bound is based on a clever iterative construction while the rounding technique we use to prove the upper bound is an adaptation of Shmoys and Tardos' rounding for the generalized assignment problem. In the second part of the paper we apply this adaptation to the more general setting in which orders, consisting of several jobs, have to be processed on unrelated parallel machines so as to minimize the sum of weighted completion times of the orders. We obtain the first constant factor approximation algorithms for the preemptive and nonpreemptive case, improving and extending a recent result by Leung et. al.

We give an introduction into the fascinating area of flows over time—also called “dynamic flows” in the literature. Starting from the early work of Ford and Fulkerson on maximum flows over time, we cover many exciting results that have been obtained over the last fifty years. One purpose of this chapter is to serve as a possible basis for teaching network flows over time in an advanced course on combinatorial optimization.

Algorithmica, 47 (3), ISSN:0178-4617, ISSN:1432-0541

Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the problem in mathematical terms yields a class of network flow problems where we group the arcs and pay in each group only for the arc carrying the maximum flow. We develop (fully) combinatorial approximation heuristics suitable for being implemented in the hardware of a control device that drives an OLED display.

We consider parallel, identical machine scheduling problems where the jobs are subject to precedence constraints, release dates, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the expected value of the total weighted completion time. Building upon a linear programming relaxation by Möhring, Schulz and Uetz (Journal of the ACM 46, 1999, 924-942) and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein (SIAM Journal on Computing 31, 2001, 146-166) we derive the first constant-factor approximation algorithms for this model.

Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by β times the size of the arriving job. Our main result is a linear time 'online approximation scheme', that is, a family of online algorithms with competitive ratio 1 + ∈ and constant migration factor β(∈), for any fixed e > 0. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited 'local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors β = 2 and β = 4/3, respectively. Their competitive ratio 3/2 beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.

In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired or even forbidden in many applications. Kleinberg introduced the unsplittable flow problem where all flow traveling from a source to a destination must be sent on only one path. This is a generalization of the NP-complete edge-disjoint paths problem. In particular, the randomized rounding technique of Raghavan and Thompson can be applied. A generalization of unsplittable flows are k-splittable flows where the number of paths used by a commodity i is bounded by a given integer k i .

Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks. While the 'maximum s-t-flow over time' problem can be solved efficiently and 'min-cost flows over time' are known to be NP-hard, the complexity of (fractional) 'multicommodity flows over time' has been open for many years. We prove that this problem is NP-hard, even for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.

Traditionally, flows over time are solved in time-expanded networks which contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static flows, its main and often fatal drawback is the enormous size of the time-expanded network. In particular, this approach usually does not lead to efficient algorithms with running time polynomial in the input size since the size of the time-expanded network is only pseudo-polynomial.We present two different approaches for coping with this difficulty. Firstly, inspired by the work of Ford and Fulkerson on maximal s-t-flows over time (or 'maximal dynamic s-t-flows'), we show that static, lengthbounded flows lead to provably good multicommodity flows over time.These solutions not only feature a simple structure but can also be computed very efficiently in polynomial time.Secondly, we investigate 'condensed' time-expanded networks which rely on a rougher discretization of time. Unfortunately, there is a natural tradeoff between the roughness of the discretization and the quality of the achievable solutions. However, we prove that a solution of arbitrary precision can be computed in polynomial time through an appropriate discretization leading to a condensed time expanded network of polynomial size. In particular, this approach yields a fully polynomial time approximation scheme for the quickest multicommodity flow problem and also for more general problems.

Motivated by applications in road traffic control, we study flows in networks featuring special characteristics. In contrast to classical static flow problems, time plays a decisive role. Firstly, there are transit times on the arcs of the network which specify the amount of time it takes for flow to travel through a particular arc; more precisely, flow values on arcs may change over time. Secondly, the transit time of an arc varies with the current amount of flow using this arc. Especially the latter feature is crucial for various real-life applications of flows over time; yet, it dramatically increases the degree of difficulty of the resulting optimization problems.Most problems dealing with flows over time and constant transit times can be translated to static flow problems in time-expanded networks. We develop an alternative time-expanded network with flow-dependent transit times to which the whole algorithmic toolbox developed for static flows can be applied. Although this approach does not entirely capture the behavior of flows over time with flow-dependent transit times, we present approximation results which provide evidence of its surprising quality.

In network scheduling a set of jobs must be scheduled on unrelated parallel processors or machines which are connected by a network. Initially, each job is located on some machine in the network and cannot be started on another machine until sufficient time elapses to allow the job to be transmitted there. This setting has applications, e. g., in distributed multi-processor computing environments and also in operations research; it can be modeled by a standard parallel machine environment with machine-dependent release dates.We consider the objective of minimizing the total weighted completion time.The main contribution of this paper is a provably good convex quadratic programming relaxation of strongly polynomial size for this problem. Until now, only linear programming relaxations in time- or interval-indexed variables have been studied. Those LP relaxations, however, suffer from a huge number of variables. In particular, the best previously known relaxation is of exponential size and can therefore not be solved exactly in polynomial time. As a result of the convex quadratic programming approach we can give a very simple and easy to analyze randomized 2-approximation algorithm which slightly improves upon the best previously known approximation result. Furthermore, we consider preemptive variants of network scheduling and derive approximation results and results on the power of preemption which improve upon the best previously known results for these settings.

In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to so-called time-indexed LPs as probabilities. The most general model we consider is scheduling unrelated parallel machines with release dates (or even network scheduling) so as to minimize the average weighted completion time. The crucial idea for these multiple machine problems is not to use standard list scheduling but rather to assign jobs randomly to machines (with probabilities taken from an optimal LP solution) and to perform list scheduling on each of them.

Three characteristics encountered frequently in real-world machine scheduling are jobs released over time, precedence constraints between jobs, and average performance optimization. The general constrained one-machine scheduling problem to minimize the average weighted completion time not only captures these features, but also is an important building block for more complex problems involving multiple machines.

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.