Search

Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual flows sent later on. In these networks, node potentials correspond to physical quantities such as pressures or hydraulic heads and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of robust network topologies for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness.

We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties, such as voltages or pressures, are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks, such as electricity, gas, or water networks. In contrast to Kron’s reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grants CRC/TRR 154, 239904186, Subproject A07].

In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., $$y_a\approx x_a$$ y a ≈ x a for all arcs a. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17–41, 1999) proved that there exists an unsplittable flow y such that $$y_a\le x_a+d_{\max }$$ y a ≤ x a + d max for all arcs a, where $$d_{\max }$$ d max denotes the maximum demand value. Our first contribution is a considerably simpler one-page proof for this classical result, based upon an entirely new approach. Secondly, using a subtle variant of this approach, we obtain a new result: There is an unsplittable flow y such that $$y_a\ge x_a-d_{\max }$$ y a ≥ x a - d max for all arcs a. Finally, building upon an iterative rounding technique previously introduced by Kolliopoulos and Stein (SIAM J Comput 31:919–946, 2002) and Skutella (Math Program 91:493–514, 2002), we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case when demands are integer multiples of each other. For arbitrary demand values, we prove the weaker simultaneous bounds $$x_a/2-d_{\max }\le y_a\le 2x_a+d_{\max }$$ x a / 2 - d max ≤ y a ≤ 2 x a + d max for all arcs a.

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $$\mathsf {APX}$$ APX -hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.

The following game is played on a weighted graph: Alice selects a matching M and Bob selects a number k. Alice’s payoff is the ratio of the weight of the k heaviest edges of M to the maximum weight of a matching of size at most k. If M guarantees a payoff of at least α then it is called α-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a [Formula: see text]-robust matching, which is best possible. We show that Alice can improve her payoff to 1/ln(4) by playing a randomized strategy. This result extends to a very general class of independence systems that includes matroid intersection, b-matchings, and strong 2-exchange systems. It also implies an improved approximation factor for a stochastic optimization variant known as the maximum priority matching problem and translates to an asymptotic robustness guarantee for deterministic matchings, in which Bob can only select numbers larger than a given constant. Moreover, we give a new LP-based proof of Hassin and Rubinstein’s bound.

Given a graph with “uncertainty intervals” on the edges, we want to identify a minimum spanning tree by querying some edges for their exact edge weights which lie in the given uncertainty intervals. Our objective is to minimize the number of edge queries. It is known that there is a deterministic algorithm with best possible competitive ratio 2 [T. Erlebach, et al., in Proceedings of STACS, Schloss Dagstuhl, Dagstuhl, Germany, 2008, pp. 277--288]. Our main result is a randomized algorithm with expected competitive ratio $1+1/\sqrt{2}\approx 1.707$, solving the long-standing open problem of whether an expected competitive ratio strictly less than 2 can be achieved [T. Erlebach and M. Hoffmann, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 116 (2015)]. We also present novel results for various extensions, including arbitrary matroids and more general querying models.

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.

The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than $+\frac{19}{14} D$, where $D$ is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998), who obtained a slightly larger bound of $+\frac32 D$. We also present an improved lower bound of $\frac{11}{10} D$ (previously $\frac{101}{100} D$) on the best possible bound and disprove a famous long-standing conjecture of Schrijver, Seymour, and Winker in this context.

We consider online versions of the minimum spanning tree (MST) problem and the traveling salesman problem (TSP) where recourse is allowed. The nodes of an unknown graph with metric edge cost appear one by one and must be connected in such a way that the resulting tree or tour has low cost. In the standard online setting, with irrevocable decisions, no algorithm can guarantee a constant-competitive ratio. In our model we allow recourse actions by giving a limited budget of edge rearrangements per iteration. It has been an open question for more than 20 years whether an online algorithm equipped with a constant (amortized) budget can guarantee constant-approximate solutions. As our main result, we answer this question affirmatively in an amortized setting. We introduce an algorithm that maintains a nearly optimal tree when given a constant amortized budget. Unlike in classical TSP variants, the standard double-tree and shortcutting approach does not give constant guarantees in the online setting. We propose...

Network flows over time form a fascinating area of research. They model the temporal dynamics of network flow problems occurring in a wide variety of applications. Research in this area has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models. In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.

The natural linear programming formulation of the maximum s-t-flow problem in path variables has a dual linear program whose underlying polyhedron is the dominant $${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$$of the s-t-cut polytope. We present a complete characterization of $${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$$with respect to vertices, facets, and adjacency.

Earliest arrival flows capture the essence of evacuation planning. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink “as quickly as possible.” The latter requirement is made more precise by the earliest arrival property, which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the successive shortest-path algorithm for min-cost flow computations. Although it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open for many years. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.

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.

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Traditionally, flows over time are solved in time-expanded networks that 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. We present several approaches for coping with this difficulty. First, 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 length-bounded flows lead to provably good multicommodity flows over time. Second, we investigate “condensed” time-expanded networks which rely on a rougher discretization of time. 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, our approach yields fully polynomial-time approximation schemes for the NP-hard quickest min-cost and multicommodity flow problems. For single commodity problems, we show that storage of flow at intermediate nodes is unnecessary, and our approximation schemes do not use any.

In many scheduling applications it is required that the processing of some job be postponed until some other job, which can be chosen from a pregiven set of alternatives, has been completed. The traditional concept of precedence constraints fails to model such restrictions. Therefore, the concept has been generalized to so-called AND/OR precedence constraints which can cope with this kind of requirement. In the context of traditional precedence constraints, feasibility, transitivity, and the computation of earliest start times for jobs are fundamental, well-studied problems. The purpose of this paper is to provide efficient algorithms for these tasks for the more general model of AND/OR precedence constraints. We show that feasibility as well as many questions related to transitivity can be solved by applying essentially the same linear-time algorithm. In order to compute earliest start times we propose two polynomial-time algorithms to cope with different classes of time distances between jobs.

We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly NP-hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection.

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent $\alpha$-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least $e/(e-1) \approx 1.5819$. Both algorithms may be derandomized; their deterministic versions run in O(n2) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a $(2+\varepsilon)$-approximation algorithm for the model with individual job release dates and a $(3/2+\varepsilon)$-approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation. It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee.

We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion times. This problem is NP-hard in the strong sense. The best approximation result known so far was a \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} ${1\over 2}1 + \sqrt{2}$ \end{document} -approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, our result constitutes the first known approximation scheme for a strongly NP-hard scheduling problem with minsum objective.

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.

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem.

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.

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.