Fairness in Routing and Load Balancing


 Paul Stafford
 5 years ago
 Views:
Transcription
1 Fairness in Routing and Load Balancing Jon Kleinberg Yuval Rabani Éva Tardos Abstract We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria interacts in a complex fashion with the optimization of network utilization and throughput; in this work, we undertake an investigation of this relationship through the framework of approximation algorithms. In a range of settings including both highspeed networks and Internet applications, maxmin fairness has emerged as a widely accepted formulation of the notion of fairness. Informally, we say that an allocation of bandwidth is maxmin fair if there is no way to give more bandwidth to any connection without decreasing the allocation to a connection of lesser or equal bandwidth. Given a collection of transmission routes, this criterion imposes a certain equilibrium condition on the bandwidth allocation, and some simple flow control mechanisms converge quickly to this equilibrium state. Indeed, the vast majority of previous work on maxmin fairness has focused on this issue of associating rates with connections that are specified by a fixed set of paths. Very little work has been devoted to understanding the relationship between the way in which one selects paths for routing, and the amount of throughput one obtains from the resulting maxmin fair allocation on these paths. In this work we consider the problem of selecting paths for routing so as to provide a bandwidth allocation that is as fair as possible (in the maxmin sense). We obtain the first approximation algorithms for this basic optimization problem, for singlesource unsplittable routings in an arbitrary directed graph. Special cases of our model include several fundamental load balancing problems, endowing them with a natural fairness criterion to which our approach can be applied. Our results form an interesting counterpart to earlier work of Megiddo, who considered maxmin fairness for singlesource fractional flow. The optimization problems in our setting become NPcomplete, and require the development of new techniques for relating fractional relaxations of routing to the equilibrium constraints imposed by the fairness criterion. A preliminary version of this work appeared at the 1999 IEEE Symposium on Foundations of Computer Science. Dept. of Computer Science, Cornell University, Ithaca NY Supported in part by an Alfred P. Sloan Research Fellowship, an ONR Young Investigator Award, NSF Faculty Early Career Development Award CCR , and BSF grant Computer Science Department, Technion IIT, Haifa 32000, Israel. Work at the Technion supported by BSF grant number , Ministry of Science contract # , and by the Fund for the Promotion of Research at the Technion. Dept. of Computer Science, Cornell University, Ithaca NY Research partially supported by NSF grant CCR , ONR grant N , and BSF grant
2 1 Introduction Fairness in routing. A basic problem in network optimization is the efficient routing of traffic between pairs of terminal nodes that wish to communicate. One of the fundamental notions that arises in such a setting is that of fairness; we want to allocate bandwidth to the connections in a way that does not unnecessarily starve any of them. Although it is an intuitively natural concept, finding a concrete definition of fairness that captures the goals of efficient routing is a subtle issue we wish to prevent starvation of individual connections in a way that allows all connections the opportunity to receive as large a bandwidth allocation as possible. An elegant framework that has gained wide acceptance in the networking community is the notion of maxmin fairness [2, 5] it forms the basis for bandwidth allocation in both highspeed networks and a range of Internet applications. It is defined via a type of equilibrium: An allocation of bandwidths, or rates, to a set of connections is said to be maxmin fair if it is not possible to increase the allotted rate of any connection while decreasing only the rates of connections which have larger rates. In other words, no connection can increase its bandwidth at the expense of connections which are better off than it is. This turns out to be equivalent to another natural definition of fairness that the list of allotted rates, when sorted in increasing order, is lexicographically as great as possible. This lexicographic definition allows one to directly compare different bandwidth allocations, and speak of the fairest allocation. The vast majority of work on maxmin fairness has focused on the setting in which connections are specified by a fixed set of paths, and one wants to associate rates with these paths. It is easy to show that the maxmin fair allocation for a fixed set of paths is unique, and a number of simple, efficient algorithms have been developed to compute this allocation (e.g. [1, 2, 5]). A wide range of network routing protocols employ such algorithms to enforce maxmin fairness (or a close approximation) on the paths used for routing connections. Note that all of this takes place, however, after the paths themselves have been chosen; very little work has been devoted to understanding the relationship between the way in which one selects paths for routing, and the amount of throughput one obtains from the resulting fair allocation on these paths. Suppose we want to select paths for routing so as to provide a bandwidth allocation that is as fair as possible (in the maxmin sense); how should we go about doing this? Megiddo [12] addressed this problem in the setting of singlesource fractional flow, in which flow must be sent fractionally to a collection of terminals from a common source, and provided an elegant polynomialtime algorithm. In this work, we consider the setting in which each connection must be routed on a single path i.e. we seek an unsplittable flow. The singlesource case here presents qualitatively new issues from those encountered in Megiddo s setting, for we can show that the fundamental analogue of his problem is now NPcomplete. A number of basic load balancing problems arise naturally as special cases of this singlesource unsplittable flow model. We obtain the first approximation algorithms for the problem of optimizing over path selection to provide the fairest possible routing. The issues that arise in this framework turn out to involve a number of interesting and very basic tradeoffs between the throughput and the type of equilibrium constraints imposed by maxmin fairness. We now provide a concrete formulation of these optimization problems, and then summarize our results in more detail. 2
3 Formulating the problem: Maxmin fairness and approximation guarantees. We seek routings from a common source node to a collection of terminals in a network. A routing, in the present framework, consists of two components the choice of paths that the traffic will use, and the allocation of available bandwidth on these paths to the different connections. Thus, let G = (V, E) be a directed graph with a capacity c e 0 on each edge. We designate a source s V and a set of terminals t 1,..., t k V. A routing of the terminals consists of a set of paths {P 1,..., P k } with P i a path from s to t i and an allocation vector r = (r 1, r 2,..., r k ). We view the st i connection as being assigned path P i, with bandwidth allocation, or rate, r i. We say that this routing is feasible if, for all edges e, the total bandwidth allocated for paths using e is at most c e ; that is, the sum of r i over all P i containing e is at most c e. One can derive maxmin fairness from the following intuitive approach to finding the fairest allocation: One should first make sure that the minimum bandwidth given to any connection is as large as possible; then, ignoring this minimum connection, one should make sure that the minimum bandwidth given to any of the connections that can still get additional bandwidth is as large as possible; and so on. More formally, given two ktuples of numbers z = (z 1,..., z k ) and z = (z 1,..., z k), each in nondecreasing order, we say that z lexicographically dominates z if z = z, or there is some index j for which z j > z j and z i = z i for all i < j. Given two allocation vectors r and r, we say that r is as fair as r (written r r) if the sorted order of the coordinates of r lexicographically dominates the sorted order of the coordinates in r. We will say that r and r are equivalent if both r r and r r. This relation defines a total order on the equivalence classes of allocation vectors; the vectors in the unique maximal equivalence class under are thus the fairest allocations. One can also use the following equivalent definition of a routing with allocation vector r being fairest in the maxmin sense: There is no way to increase any entry r i without decreasing some other entry r j such that r j r i. As we discussed above, maxmin fairness in the networking community has been applied primarily to the setting in which one is given not only a set of connections in a network, but also the paths {P i } that they are to use. Thus the only issue is to determine the allocation vector, which is unique in this case; and this can be accomplished by a variety of efficient algorithms (see e.g. [1, 2, 5]). Network protocols that employ maxmin fairness thus enforce the following maxmin equilibrium condition: ( ) For any routing with paths {P i } and allocation vector r, r must be a fairest allocation given the paths P i. The crucial issue raised in the discussion above is then the following. We wish to choose paths for routing a set of connections, with the bandwidth allocation vector then uniquely determined by the equilibrium condition ( ). The amount of bandwidth utilization in a fairest allocation depends heavily on the set of paths {P i } that one chooses; some choices of paths allow for much greater fair utilization of the network than others. The fundamental question we seek to address is that of determining the fairest routing, optimizing over all possible choices of paths, with the allocation vector determined by ( ). For example, does the fairest routing achieve the maximum possible throughput of any routing? This was the precise problem considered by Megiddo [12] in the context of the singlesource fractional flow problem, in which all connections share a common endpoint, but one can divide the flow for a single connection fractionally over many paths. In addition to providing a polynomialtime algorithm for computing a fairest routing, he showed that the fairest flow is a maximum flow with fractional flow, one does not sacrifice throughput by imposing fairness. 3
4 In this work, we focus on the analogous problem, computing a fairest routing, in the setting of singlesource unsplittable flow [3, 8, 9]. Once we move to unsplittable flow, the basic problem becomes NPcomplete, even in the unitcapacity case with all c e equal to 1. More precisely, we can prove that the following decision problem is NPcomplete in the unitcapacity case: given G, s, the terminals {t i }, and a vector r, is there a routing of the terminals for which the allocation vector r satisfies r r? Additionally, we can show that the fairest flow need not be a maximum unsplittable flow. In view of this NPcompleteness result, we focus on obtaining both general approximation algorithms and exact algorithms for polynomialtime special cases. The optimization problems here are over the ordering on allocation vectors defined by fairness hence, since there is no single numerical measure, we must be careful in how we define our notion of approximation to the optimum. We propose the following two natural definitions of approximation. First, we say that r is a coordinatewise capproximation to r if for each j, the j th smallest entry in r is at least 1/c times the value of the j th smallest entry in r. As a weaker notion, we say that r is a prefixsum capproximation to r if for each j, the sum of the j smallest entries in r is at least 1/c times the sum of the j smallest entries in r. In other words, a prefixsum approximation ensures that the subsets of terminals with the smallest allocations receive sufficient bandwidth. When we move to approximate solutions, it is very important that we can keep in mind that the equilibrium condition ( ), or a relaxed version of ( ), serves as an additional feasibility requirement on the solutions we can produce: in effect, we are able to choose only the paths P i, for then the network uses ( ) to enforce the unique equilibrium allocation vector r. (Of course, in the fairest routing, the allocation r will necessarily be in equilibrium.) This requirement rules out, for example, the following simple approach based on the DinitzGargGoemans unsplittable flow approximation algorithm [3]: compute the fairest fractional flow using Megiddo s algorithm, scale all resulting allocations down by a factor of 2, and route them as unsplittable demands. The problem is that these scaled demands are generally very far from equilibrium for the paths used. For example, if the fairest fractional flow has allocations of widely varying magnitude, it is easy to find examples in which the DinitzGargGoemans algorithm produces a routing where flow paths with both small and large allocation share edges, and the allocation vector is arbitrarily far from satisfying the equilibrium condition ( ). All previous singlesource unsplittable flow algorithms [8, 9] exhibit the same problem. Summary of results: Routing. For the singlesource unsplittable flow problem on an arbitrary directed graph with unit capacities, we indicated above that finding a fairest allocation vector is NPcomplete. We develop a general approximation algorithm for this problem by relaxing both the optimality and the equilibrium requirements. First, what do we mean by relaxing the equilibrium requirements? For a constant c, we say that an allocation vector r is in a state of capproximate equilibrium if it is not possible to raise the value of an entry r i without decreasing some other entry r j such that r j cr i. Thus, 1approximate equilibrium indeed corresponds to maxmin equilibrium; we believe that approximate relaxations of these natural equilibrium notions raise a number of interesting issues in their own right. We give an algorithm that produces a routing whose allocation is in 2approximate equilibrium, and is a coordinatewise 2approximation to the allocation of the fairest fractional routing. We develop the algorithm by computing a fairest flow for the following discretized version of the fairest routing problem. Suppose we only consider routings whose allocation vectors 4
5 have entries that are all inverse powers of two; we will call such routings and allocation vectors binary. Then we can restrict our fairness ordering to binary allocation vectors, and seek a fairest allocation of this type. We show how to find a fairest binary routing in polynomial time, for the singlesource unsplittable flow problem on an arbitrary unitcapacity directed graph G. It is not difficult to show that the fairest binary routing we obtain is both a coordinatewise 2approximation to the unrestricted fractional optimum, and in a state of 2approximate equilibrium. The fairest binary routing has a number of other desirable properties. Specifically, recall from the discussion above that the fairest unsplittable flow need not be a maximum unsplittable flow. However, as a direct consequence of our construction of fairest binary flows, we find that there is a fairest binary flow whose total throughput is equal to that of the maximum fractional flow. Thus, by optimizing over binary routings rather than arbitrary unsplittable routings, we do not sacrifice throughput when we impose the fairness condition. We find the existence of a polynomialtime algorithm for fairest binary routings somewhat surprising, given that the same problem for unrestricted routings is NPcomplete. As a basic building block in the algorithm, we first establish the special case that if all terminals can be routed with at most two paths on any edge, then the fairest unrestricted routing (which will be binary) can be computed in polynomial time. We then apply this result over increasingly large cuts in the graph G to piece together an optimal binary flow. A natural problem is to provide a good approximation to the fairest unsplittable routing in an arbitrary directed graph without relaxing the equilibrium condition ( ); we leave this as an open question. Summary of results: Load Balancing. The setting of singlesource unsplittable flow contains a range of load balancing problems. We begin by providing algorithms for two of the most natural of these without relaxing the equilibrium condition ( ). First, the singlesource unsplittable flow problem on a twolevel unitcapacity graph is equivalent to the following load balancing problem: we have a set of jobs J = {J 1,..., J k }, and a set of machines M = {M 1,..., M n }; for each job J i, there is a set S i M on which J i can be run. Each machine has the same processing power. We wish to assign each job to a machine, and our fair allocation vector r = (r 1,..., r k ) specifies the fraction of processing power each job J i receives on its assigned machine. We will call this the uniform load balancing problem. More generally, each job J i can have an upper bound u i on the amount of processing power it wants. In this setting, we will only consider allocation vectors r for which r i u i for each i. We will call this the nonuniform load balancing problem; this problem too can be encoded in the singlesource unsplittable flow problem, with the upper bounds u i appearing as capacities. We first show that a fairest allocation vector for the uniform load balancing problem can be computed in polynomial time. This can be viewed as a natural analogue of Megiddo s result to a setting with unsplittable assignments; the tractability of the problem comes essentially from its connection with bipartite matching, although it is important to note that the allocations in the optimal fractional and integer flows are not the same. Finding a fairest allocation for the nonuniform load balancing problem is NPcomplete; indeed, even determining whether every job can achieve its upper bound u i is an NPcomplete 5
6 problem considered by Lenstra, Shmoys, and Tardos [10]. We give a polynomialtime algorithm that produces a prefixsum 2approximation to the fairest allocation. The approximate allocation we produce is (following our discussion above) in maxmin equilibrium. We begin from a fairest fractional allocation of jobs to machines here the allocation of one job J i can be spread over several machines in its set S i computed via Megiddo s algorithm. We then build on the fractional rounding algorithm in [10] to obtain the approximation. Our prefixsum approximation in fact shows a type of integrality gap in this multicoordinate setting; it is a prefixsum 2approximation to the optimal fractional allocation. We will describe simple examples in which there cannot be a coordinatewise O(1)approximation to this fractional optimum. Organization. The remaining three sections of the paper can be read independently. Section 2 develops the algorithms for the load balancing problem without relaxing the equilibrium condition ( ). In Section 3 we consider the singlesource fair unsplittable flow problem on an arbitrary unit capacity directed graph. We develop a general approximation algorithm for this problem by relaxing both the optimality and the equilibrium requirements. Finally, Section 4 shows that the singlesource unsplittable fair flow problem is NPcomplete on unit capacity directed graphs. 2 Fair Load Balancing Algorithms The fair load balancing problem is concerned with assigning jobs to machines. Assume that we have a set of jobs J = {1,..., k}, and a set of machines M = {M 1,..., M n }; and for each job j, there is a set S j M on which job j can be run. An assignment is a function F : J M so that F assigns each job j to a machine in S j. First we consider the special case of the uniform load balancing problem, and show that an optimum fair solution can be found in this case. Then we consider extensions to problems where the jobs have different needs. Uniform Load Balancing The uniform fair load balancing problem can be restated as follows. We want to assign jobs to machines, and choose a load l j for each job j so that the following two conditions hold. First, if A(i) denotes the set of jobs assigned to machine M i, we must have that j A(i) l j 1. Second, the set of allocated loads sorted from smaller to larger should be lexicographically maximal. If we are given an assignment of jobs to machines the corresponding fair loads are very easy to compute: Lemma 2.1 Given an assignment of jobs to machines, the fairest allocation load is to assign load l j = 1 d i to job j, where job j has been assigned to a machine M i with d i = A(i). This lemma simply represents the constraint imposed by the equilibrium condition ( ). Our goal is now to optimize over all assignments of jobs to machines. Based on Lemma 2.1, our primary objective is to minimize d max = max i A(i), the maximum number of jobs that go on the same machine. Our secondary objective function is to have as few jobs as possible assigned to such highly loaded machines, and so on. We obtain the following equivalent formulation of the load balancing problem. In an assignment F let d i denote the number of jobs assigned to 6
7 machine M i ; corresponding to the standard view of assignment problems in terms of bipartite graphs, we will also refer to d i as the degree of M i. Lemma 2.2 The uniform fair load balancing problem is equivalent to finding an assignment F so that the sequence of degrees d i for i = 1,..., m when sorted from large to small is lexicographically as small as possible. We will use F more generally to denote a possibly partial assignment of jobs to machines; we write F to denote the number of jobs assigned by F. We say that F is a (partial) assignment of maximum degree d if the maximum number of jobs assigned to a machine is d, and F is a maximum assignment of degree at most d if the number of unassigned jobs is the least possible among all assignments of degree at most d. Given any assignment F of jobs to machines of degree at most d, we can use augmenting paths to find a maximum assignment F of degree at most d. We will refer to this process as Augment(F, d). Our load balancing algorithm starts with F 0 =, and defines F d =Augment(F d 1, d) iteratively for d = 1, 2,... until all jobs get assigned. The assignment at termination is then returned; we denote this assignment F. The assignment found by F =Augment(F, d) has the following properties. First, all jobs assigned in F are also assigned in F. Second, if d i and d i denotes the degree of machine M i in assignments F and F then d i d i. Both of these properties follow from the augmenting path algorithm: augmenting paths never use the backwards edges leaving the sink or entering the source. These two properties imply that the final assignment F in a sense contains an optimum assignment for all degrees d. Let d i be the number of jobs assigned to machine M i by the final assignment F. Then we have the following. Lemma 2.3 For all integers d we have that F d = i min(d i, d). Further, if the degree of a machine i is less than d in assignment F d, then the degree will not change throughout the rest of the algorithm. Proof. The first statement will follow from the monotonicity of the degrees during the augmentations. Consider assignment F d. The augmentations done after this assignment will not decrease the degrees due to the monotonicity property. Hence F d i min(d i, d). The right hand side is the size of the assignment of maximum degree d obtained by deleting edges from F entering nodes of degree more than d. The matching F d is a maximum such matching, so we also have the opposite inequality F d i min(d i, d). The second statement follows immediately from the first one and the monotonicity of the degrees. The essence of why this algorithm is optimal is contained in the following lemma. Let r d = k F d denote the number of unassigned jobs in the maximum assignment of degree d. Lemma 2.4 Let F be the assignment found the algorithm, and F some other assignment. For any degree d let f d and f d denote the number of machines of degree d in F and F respectively; let r d denote the minimum possible number of unassigned jobs in an assignment of maximum degree d. We have that r d f d+1 + 2f d+2 + 3f d , r d = f d+1 + 2f d+2 + 3f d
8 Proof. To see the first statement, we can delete edges out of F to create a matching of maximum degree d. We need to delete i edges from each machine with degree d + i, so the right hand side is the number of unassigned jobs at the end of this process. This is at least r d by the definition of r d. To see the second statement we use the lemma above. Deleting i edges from each machine of degree d + i, we recreate the degree sequence of F d, hence the number of jobs unmatched at the end of this process is exactly r d = k F d. The lemma immediately implies that the assignment M is optimum. Theorem 2.5 The algorithm above finds the optimum assignment of jobs to machines for the load balancing problem. NonUniform Load Balancing Next we consider a more general version of the fair load balancing problem on machines. We will still assume that machines are uniform, in that the maximum possible load of each machine is the same. However, jobs will no longer be uniform. Assume that we have an upper bound u j for the amount of processing power a job j can use. Now an assignment of jobs to machines, and loads l j for each job j, must satisfy the following. (i) l j u j. (ii) If A(i) denotes the set of jobs assigned to machine i, we must have that j A(i) l j 1. (iii) The allocation of loads to jobs satisfies the maxmin equilibrium condition ( ): we cannot increase the load of one job j with l j < u j without decreasing the load of some other job j that has l j l j. We can think of this assignment problem as a flow problem in the following threelayer graph. We have a source s connected to nodes representing each of the machines M i with an edge of capacity 1. There is an edge of infinite capacity from machine node i to job node j if M i belongs to S j. Finally there is an edge from each job node j to a corresponding terminal t j with capacity u j. A fairest fractional flow [12] in this network corresponds to a fairest fractional assignment of job loads to machines. Let f denote this fairest fractional assignment, and let l j denote the load of job j in f. We say that a job j is integrally assigned to machine M i is the entire allocation of job j is to machine i; otherwise, we say that it is partially assigned to those machines on which it receives a strictly positive allocation. An assignment F of jobs to machines is integral if all jobs are integrally assigned by F. At various points, we will use the notation A(i) to refer to the set of jobs assigned to a machine M i. For an integral assignment of jobs to machines, the fairest allocation of loads can be computed on each machine independently, and it has a very simple form that follows from the definition of maxmin equilibrium. For a real number x [0, 1], let B(x) be the allocation of loads to jobs in a set A(i) defined by allocating min(u j, x) to each job j A(i); the total load allocated by B(x) is the sum j A(i) min(u j, x). Then we have Lemma 2.6 The fairest allocation of load to A(i) is B(x ), where x is the maximum x [0, 1] for which the total load of B(x) is 1. The parameter x can thus be viewed as a critical load that caps the allocation to jobs whose upper bound u j is too large. We can formulate this notion in a way that also extends to fractional assignments of jobs to machines, as follows. 8
9 Lemma 2.7 In a (possibly fractional) assignment of jobs to machines, the fairest allocation of loads to the set A(i) has the following property. The machine M i has an associated critical load m i ; and the load of any job j A(i) is l j = min(m i, u j ). For each machine, either the machine is fully loaded, or m i = max(u j ) over all j A(i). Further, if some job j A(i) does not achieve its upper bound u j, then m i = min j A(i):l j <u j l j. That is, m i is the minimum load among jobs on M i that are not able to achieve their upper bounds. In our algorithm, we will construct an integral assignment of jobs to machines, and then use the fairest allocation of load given by Lemma 2.6. Notice that finding the fairest assignment is NPhard, as deciding if there is an assignment in which all jobs can be assigned their maximum load l j = u j is a standard NPhard scheduling problem [10]. Our goal will be to make the resulting loads closely approximate the load sequence of the fractional assignment. Instead of a coordinatewise approximation of loads, we will give a prefixsum 2approximation. We observe that it might not be possible to approximate the vector of fairest fractional loads l 1, l 2,... with a fair integer assignment. Consider, for example, a problem in which we have n machines M 1,..., M n. Assume that the first job can be assigned to any machine, and has u 1 = 1. In addition to this job, for each machine M i, there are n 1 jobs with u j = 1/n that can only be assigned to M i. Now fractionally, we can assign each job its maximum load l j = u j by spreading the load of job 1 across all machines. However, in any integer assignment, the fair load for that assignment will have l 1 = 1/n; i.e., there is no way to approximate the optimal fractional fair load of job 1 in an integer assignment. We use Megiddo s algorithm [12] to obtain a fairest fractional flow f. We then use the rounding algorithm of Lenstra, Shmoys and Tardos [10] to create an integral assignment F from f. Let A(i) be the set of jobs assigned to machine M i by F, and let l A j denote the fair load of this assignment. Theorem 2.8 ([10]) Assume f is a fractional assignment of jobs to machines assigning load l j to job node j. The approximation algorithm of [10] constructs an integral assignment F so that for each machine M i, A(i) consists of all the jobs that were integrally assigned to M i by f, plus at most one additional job that was partially assigned to M i. Since f did not assign more than 1 unit of load to any machine, we consequently have j A(i) l j 1 + max j A(i) l j. First we analyze the fair loads of the set of jobs A(i) for a single machine M i. Let j i denote the job with maximum load l j in A(i), Lemma 2.9 The fair load of all jobs j A(i) with the possible exception of job j i have l j 2l A j. Proof. We say that M i is saturated by f if some job j that was integrally assigned to M i by f has a load l j < u j. Let m i denote the critical load (in the sense of Lemma 2.7) of machine M i in the fairest fractional assignment f. We define m i to be m i if M i is saturated by f; otherwise, we define m i to be the maximum of u j over all jobs j that were integrally assigned to M i by f. In the analysis, we consider the allocation B(m i/2) and show that it has total load 1. It then follows that any job that was integrally assigned to M i has integral fair load at worst a factor of two smaller than its allocation in the fractional solution. Moreover, if j A(i) is the unique job that was partially assigned to M i by f, and its load decreases by more than a factor 9
10 of two, then we must have l j > m i, whence j is the job of maximum load, and constitutes the exceptional job in the statement of the lemma. Thus it remains only to prove that B(m i/2) has total load at most 1. To see this, we consider two cases, depending on whether or not M i is saturated by f. If M i is saturated, then some job that was integrally assigned to M i is given load m i by f; in B(m i/2) this job s load decreases by m i/2 and creates enough room for one extra job with load at most m i/2. If M i is not saturated, then m i = u j for some integrally assigned job j; again, in B(m i/2) this job s load decreases by m i/2, creating room for an extra job with load at most m i/2. Theorem 2.10 Let l A j denote the load of job j in the assignment created by our algorithm. For each h the sum of the h smallest loads of l A j is at least a half of the sum of the smallest h loads in the fairest fractional assignment f. Proof. Sort the jobs by increasing order of their load l A j. On each machine M i the job j i has the maximum fractional load. This job will have maximum fair load l A among those assigned to M i by F, and hence we can assume that j i is the last among all jobs in A(i). Assume for this proof that the jobs are indexed in this order, i.e. l A 1 l A 2 l A j i. Consider the prefix sum t A h = j h l A j for each h. We will show that these values 2 approximate the corresponding optimum values. In particular we will show that for each h we have j h l j 2t A h. This implies the theorem: The value t A h, the sum of the smallest h loads in the algorithm s assignment, needs to be compared to the smallest h values in loads l j, whereas here we compare it to a set of h values that may not be the smallest. Consider the subset of the jobs j that are assigned to machine M i. We now show that j h,j A(i) l j 2 j h,j A(i) To see this consider two cases. Let j i be the index of the job in A(i) with maximum load l ji. If j i > h then the inequality is true term by term due to Lemma 2.9. If j i h then our assumption that j i is ordered last in A(i) implies that all jobs in A(i) participate in the sum. Now the statement follows from Lemma 2.8 as the sum of the loads in the fractional assignment is bounded by l j 1 + max l j 2. j A(i) j h,j A(i) Summing over all machines M i we get the desired bound. 3 SingleSource Fair Routing in Graphs In this section we give a 2approximation to the fairest unsplittable routing for the singlesource fair flow problem in arbitrary unitcapacity directed graphs. The problem is specified by a directed graph G = (V, E), a source s V, and terminals t 1, t 2,..., t k V (all edge capacities are 1). We first show that the fairest binary unsplittable flow, i.e., the most fair unsplittable flow whose allocation vector consists only of inverse powers of 2, can be found in polynomial time. Then we show that this binary fair flow is in 2approximate equilibrium, and is also a coordinatewise 2approximation to the fairest fractional flow. l A j. 10
11 Fair Routings of Congestion Two As a basic building block in the algorithm, we first establish the special case that if all terminals can be routed with at most two paths on any edge, then the fairest unrestricted allocation (which will be binary) can be computed in polynomial time. We will say that a set of paths has congestion two if at most two paths use any edge. The assumption that all terminals can be routed with paths of congestion two implies that there is an unsplittable flow sending.5 from s to each of the terminals. Lemma 3.1 If.5 units of flow can be routed to all terminals then the fairest unsplittable flow is a flow that routes either.5 or 1 to each terminal, sending 1 to as many terminals as possible. Our goal in this special case can be rephrased as follows. We wish to create paths from the source to each of the terminals so that the following conditions hold. (i) The set of paths has congestion two. (ii) The number of paths that are involved in shared edges is as small as possible. Given such a routing we can send a flow of value 1 on the paths that do not go through shared edges, and a flow of value.5 on all other paths. The main theorem of this subsection gives a way to find such paths in polynomial time, and also shows that there is such a routing in which the corresponding unsplittable flow is a maximum flow from s to the terminals. Theorem 3.2 Assume there are paths from s to the terminals with congestion two. Then there is a set of paths to the terminals with congestion at most two, where the number of paths that do not share edges with other paths is maximum subject to this condition, and the corresponding flow is a maximum flow from s to the terminals. This set of paths can be found in polynomial time. Proof. Let m denote the maximum number of disjoint paths from s to the terminals. Let f denote a maximum integer flow that sends at most 1 unit of flow to any terminal. For notational simplicity assume that the flow is sent to terminals t 1,..., t m, and let P 1,..., P m denote the paths used by this flow, so that P i is a path from s to t i. Let f be the flow that corresponds to the paths to the terminals with congestion two. The flow f sends.5 units of flow to each terminal. We plan to combine the flows f and f to obtain the desired paths. Consider the flow f f in the residual graph of G with respect to f. A path decomposition of this flow contains halfintegral flow paths Q m+1,..., Q k where for j = m + 1,..., k, Q j ends at terminal t j, and starts at one of the first m terminals (a different one for each path; notice that by our assumptions, m k/2). The paths P 1,..., P m and Q m+1,..., Q k satisfy the following. (i) The paths P i are disjoint. (ii) The paths Q j do not use edges of the P i paths forwards, but may use them backwards. (iii) The paths Q j have congestion at most two. Any set of paths Q m+1,..., Q k that satisfies the last two properties can be used to augment flow along the P i paths. By sending.5 units of flow along each path Q i we get a maximum flow (of value m) that sends at least.5 units of flow to each terminal. However, this is not an unsplittable flow as the augmentation might cause one unit of flow from s to t i, for some i m, use two paths. If there is a set S of 2m k of the paths P i with the property that the Q j don t use backward edges from any P i S, and don t start at the terminal associated with any P i S, then we can use each of the Q j paths to augment the flow f by.5 without affecting the one unit of flow sent 11
12 along those P i that belong to S. This means that we get the desired maximum unsplittable flow f, and a path decomposition of this flow gives the paths claimed by the theorem. Our goal is thus to modify the paths Q j for j = m + 1,..., k so as to satisfy the assumption above: If a path Q j uses one of the edges in the paths P i backwards (i.e., uses the residual edge), then the corresponding terminal t i is an endpoint of a (possibly different) path Q j. Once we have such paths we can use the argument above to obtain the theorem. We will modify the paths using a process that is similar to the GaleShapley stable marriage algorithm [4]. (Indeed, we can carry out the remainder of the proof through a reduction to the stable marriage problem; however, we feel it is simpler here to provide a direct argument.) We say that paths P i and Q j meet if Q j has the terminal t i as an endpoint, or if a contiguous segment of Q j consists of backward edges from P i. Note that there may be many such meetings, in this sense, between the same pair of paths P i and Q j. Suppose a path P i meets a path Q j, but t i is not an endpoint of any path Q j. If there are many paths that meet P i, then let Q j be the path that meets P i at an edge e closest to its terminal t i. We change Q j so that it begins from this terminal t i, and continues along the backward edges of P i until the meeting point e; it then continues as before. This rerouting of a path Q j leads to an alternate set of paths that also satisfies the above properties, and hence can also be used for augmentation. We repeat this process until there are no pairs of paths P i and Q j that satisfy the condition above. We now want to argue that this process terminates; for when it does, we have the set of augmenting paths needed to find the flow f. To show termination, note that each rerouting decreases the number of distinct meetings between a path in {P 1,..., P m } and a path in {Q m+1,..., Q k }: before the rerouting, path Q j met some other path P i before meeting P i, and this meeting is now eliminated. For the next subsection we will need a version of this theorem that routes flows in smaller units. For some integer γ > 0 let v γ denote the maximum value of a flow that sends at most 1/γ flow to each terminal. By considering each edge as a set of γ parallel edges we get the following. Corollary 3.3 Assume there is a flow that routes 1/(2γ) units of flow from s to each of the terminals, then there is an unsplittable flow that routes 1/(2γ) or 1/γ units of flow to each terminal and has value v γ. Constructing a Binary Allocation In this subsection we show how to construct the fairest binary flow in polynomial time, using the algorithm of Corollary 3.3. Let 2 c be the maximum power of two such that there is a flow of value 2 c from s to all of the terminals t i. The lexicographic definition of the fairest binary flow implies that we must send at least 2 c units of flow to each terminal. We use the Corollary 3.3 with γ = 2 c 1 to find flow paths from the source to each of the terminals. Let S c denote the sside of a minimum cut of value v γ. If there are many such mincuts, let S c be the inclusionwise minimal. (We will frequently identify cuts with their ssides, hence referring to S c as a cut.) From the paths obtained above we keep only the parts after leaving the cut S c, and will recursively find beginning parts that match up with these paths. There are two facts that we need about the inclusionwise minimal mincut S c. First, any maximum flow saturates the edges leaving S c. Second, no terminal that received only 2 c flow 12
13 in the routing above is contained in S c. This latter statement follows as the minimum cut S c consists of nodes reachable in the residual graph from s, and if a terminal with only 2 c flow were reachable, then its flow could be increased. The first observation allows us to define the following smaller problem that we solve recursively. Let the graph G be obtained from G by considering the subgraph on S c and adding to this graph all the edges leaving S c. We keep all terminals in S c, and replace the terminals outside of S c by 2 c 1 new terminals at the end of each of the edges leaving S c. The second property of S c implies that in the new problem there is a flow that sends 2 c+1 units of flow from s to each of the terminals in G. Each edge leaving S c has 2 c 1 new terminals, and so if each of these terminals receive 2 c+1 flow then the cut S c has to be saturated. Recursively we obtain a fairest binary flow f on the subproblem on G. We obtain the solution to the original problem by taking the flow paths of the flow f to the terminals in S c. The flow paths to the new terminals at the end of the edges leaving S c are combined with the segments of the paths obtained in the first iteration to obtain the desired paths and flow. It is not hard to show by induction on c that the flow created this way is the fairest binary flow. Theorem 3.4 The algorithm given above constructs a fairest binary flow. A simple corollary of the construction is the following. Corollary 3.5 There are nested cuts S c for c = 1, 2,..., such that S c S c+1 for all values of c, S c = V for a sufficiently large value of c, and the following property holds. In a fairest binary flow, all terminals in S 1 receive 1 unit of flow, and all terminals in S c+1 S c receive either 2 c or 2 c+1 units of flow. The Overall Approximation Guarantee Now consider the problem of finding an approximate fair flow. Our algorithm finds the fairest binary flow. We claim here that this flow satisfies our approximation guarantee. Theorem 3.6 The fairest binary flow is in 2approximate equilibrium. Proof. We use Corollary 3.5 for the proof. Suppose a terminal t i receives 2 c units of flow. We need to prove that we cannot increase the flow to t i without decreasing the flow to some other terminal t j that receives at most 2 c+1 units of flow. Consider the cut S c in the Corollary. The terminal t i is on the sink side of S c. The cut S c is saturated, so we cannot increase the flow to t i without decreasing some other flow across the cut S c. However, all terminals on the sink side of S c receive at most 2 c+1 units of flow. It is easy to see that the fairest binary flow is a prefixsum 2approximation of the fractional fair flow. This fact follows essentially as the fairest binary flow saturates the cuts S c of Corollary 3.5. We need to use more about Megiddo s optimal fractional flow algorithm to see that the binary flow is in fact a coordinatewise 2approximation of the fairest fractional flow. Theorem 3.7 The fairest binary flow is a coordinatewise 2approximation to the fairest fractional flow. 13
14 Proof. Consider the fairest fractional flow f. For any value α let T α denote the set of terminals that receive at least α flow. Megiddo proved the fairest fractional flow is a maximum flow from s to each of the sets T α simultaneously. This implies the following analogue of Lemma 2.3. For a value α let v α denote the maximum value of a flow from s to the terminals, where each terminal receives at most α units of flow. If for each terminal t i that receives some d i > α flow we delete from f d i α units of flow from s to t i, then we obtain a flow f α of value v α. Let {S c } denote the cuts of Corollary 3.5. We get the claimed coordinatewise 2approximation if we show that the fairest fractional flow f must send at most 2 c+1 units of flow to every terminal outside of S c. We prove this by contradiction. Let c be such that some terminal t i outside of S c received some d i > 2 c+1 units of flow in f. Let α = 2 c+1, and consider the flow f α. By our assumption f α does not saturate the cut S c. The fairest binary flow shows that the maximum flow value v α is equal to the capacity of the cut S c plus α times the number of terminals in S c. However, f α does not saturate the cut S c, and hence has smaller value than v α. This contradiction proves that f must have sent at most 2 c+1 units of flow to each terminal outside of S c. 4 The NPCompleteness of Fairest Allocation We formulate here a decision problem associated with computing a fairest routing, and show that it is NPcomplete. The reduction is somewhat complicated for the following reason: We are dealing with a singlesource flow problem with unit capacities, and to obtain an NPcomplete problem here, one typically needs to introduce terminals with different (unsplittable) demand values. Lacking a notion of demand in our problem, we must simulate such demands using the constraints imposed by the equlibrium condition ( ). Theorem 4.1 The following problem is NPcomplete: given a singlesource routing problem with a unitcapacity directed graph G, source s, terminals {t i }, and an allocation vector r, is there a routing of the terminals whose equilibrium allocation vector r satisfies r r? (I.e. r is at least as fair as r.) Proof. The problem is in NP since we can exhibit the paths in such a routing, and in polynomial time compute its equilibrium allocation vector in order to compare it to r. To show NPhardness, we reduce from a special case of the nonuniform load balancing problem considered by Lenstra, Shmoys, and Tardos [10]. We have a set of jobs J = {J 1,..., J k }, and a set of machines M = {M 1,..., M n }; for each job J i, there is a set S i M on which J i can be run. Each job J i has a requirement r i with the property that each r i is equal to either 1 or 1; 2 we wish to assign each job J i to a machine in S i so that the sum of the requirements assigned to each machine is at most 1. Moreover, our instance has the property that i r i = n that is, the total of the requirement values is equal to the number of machines. So the feasibility condition indeed requires that each machine receives either a single job of requirement 1 or two jobs of requirement 1. Let J J denote the jobs of requirement 1, and let J J denote 2 the jobs of requirement 1; we write 2 k = J and k = J, and observe that our condition i r i = n can be expressed as k + k /2 = n. We construct the following singlesource fair routing problem to encode this decision problem. We refer the reader to Figure 1 for the overall layout of the construction. For simplicity of presentation, we will describe certain nodes as containing several terminals; if we wish each 14
15 source s job i of req 1 u j job j of req 1/2 u j q j q j v m machine m S j q j term. t j term. t j t j k terminals w 1,..., w k four terminals t j,1,..., t j,4 subgraph H j Figure 1: The NPcompleteness reduction terminal to be identified with a distinct node, we can attach each of them via a new degreeone node. For each job J j, we create nodes u j and u j, with edges (s, u j ) and (u j, u j). For each machine M m, we create a node v m, and edges (u j, v m ) for each pair (j, m) such that machine M m belongs to the set S j. We also create a single node w that will hold k terminals w 1,..., w k, and add edges (v m, w) for each k. This defines the core of the construction, through which we encode the condition that job J j can only be assigned to a machine in S j. Moreover, if we view this portion of the graph in isolation, we can observe the following: Since there are only n edges entering w, and k terminals at w, we know that the fairest allocation for these terminals would have k entries equal to 1 and k entries equal to 1, as we want. However, we have not yet controlled which job nodes get 2 the value 1, and which get 1. This is what we accomplish in the remainder of the construction. 2 For each job J j with a requirement of 1, we attach a subgraph H 2 j containing a total of six terminals t j, t j, t j,1..., t j,4 as shown in Figure 1. We do not create anything additional for the jobs with requirement 1. Thus the complete set of terminals is the set {w i }, together with the six terminals from each of the subgraphs H j. 15
16 The subgraph H j is designed to achieve the following effect. The four terminals at t j will each get an allocation of 1/4; if one path bound for t j passes through each of q j and q j, then each of t j and t j will get an allocation of 3/4. Finally, two paths bound for t j can pass through the edge (u j, u j), leaving room for a path bound for a terminal at w to receive an allocation of 1/2. Thus, overall, the fairest allocation will allow a single path to w to get a value of 1/2. Note that for edges (u j, u j) with no subgraph H j attached, on the other hand, we can have a single path to w with an allocation of 1. We now make this precise. Define r to be a vector consisting of 4k entries equal to 1/4, k entries equal to 1/2, 2k entries equal to 3/4, and k entries equal to 1. If there is a feasible allocation of jobs to machines in the original load balancing problem, then it is easy to construct a routing whose equilibrium allocation r satisfies r r. We have a path s, u j, u j, v m, w for each job J j assigned to machine M m, with an amount of flow equal to the requirement of job J j. We have two paths s, u j, u j, q j, t j, carrying flow 1/4 each, for each job J j with requirement 1/2; these serve to saturate the edge (u j, u j). The other two terminals on t j will have paths through q j and q j respectively, carrying 1/4 units of flow; and the terminals t j and t j can then receive 3/4 units of flow each on their unique paths from s. Conversely, suppose there is a routing whose equilibrium allocation r satisfies r r. The vector r can only contain at most 4k entries equal to 1/4, so these must be associated with all the terminals of the form t j,i. Also, r can only contain at most k entries equal to 1/2, so these must be associated with paths that pass through k /2 of the edges into w. All the remaining terminals must get a flow value of at least 3/4 this therefore consists of of terminals of the form t j, t j, as well as k of the terminals at w. Each terminal of the form t j, t j must get at least a flow of 3/4, so at most one path bound for t j can pass through each of q j and q j. Hence at least two of these paths must pass through the edge (u j, u j). We claim that in fact exactly two of these paths pass through each such edge (u j, u j) (and hence exactly one passes through each of q j and q j ). For suppose that at least three passed through (u j, u j). Then no terminal bound for w could use (u j, u j), and so some edge (u l, u l) would carry two paths bound for w, each with a flow of 1/2; therefore, it would follow that no terminal from t l could make use of the edge (u l, u l), and this would force more than one path bound for t l to pass through one of q l or q l, a contradiction. Thus, k of the terminals at w get a flow value equal to 1, so we observe that at least k of the edges of the form (u j, u j) must carry a single path only. We will call these pure edges, and the other edges of the form (u j, u j) mixed. We have therefore established the following two properties of our routing with allocation at least as fair as r : There are k mixed edges of the form (u j, u j); these are associated with indices j for which J j has requirement 1/2, and on each one, there is a single path bound for w with a flow of 1/2. There are k k = k pure edges of the form (u j, u j); these are associated with indices j for which J j has requirement 1, and on each one, there is a single path bound for w with a flow of 1. Hence for each edge (u j, v m ) that carries positive flow, we can assign job J j to machine M m ; this will be a feasible assignment of jobs to machines in the original load balancing problem. 16
17 References [1] Y. Afek, Y. Mansour, Z. Ostfeld, Convergence complexity of optimistic rate based flow control algorithms, Proc. 28th ACM STOC, [2] D. Bertsekas, R. Gallager, Data Networks, PrenticeHall, [3] Y. Dinitz, N. Garg, M. Goemans, On the singlesource unsplittable flow problem, Proc. 39th IEEE FOCS, [4] D. Gale, L. Shapley, College Admissions and the Stability of Marriage, Amer. Math. Monthly 69(1962). [5] J. Jaffe, Bottleneck flow control, IEEE Trans. Communication, 29(1981), p.p [6] R.M. Karp, On the computational complexity of combinatorial problems, Networks 5(1975), pp [7] F. Kelly, Charging and rate control for elastic traffic, European Trans. Telecommunications 8(1997). [8] J. Kleinberg, Singlesource unsplittable flow, Proc. 37th IEEE FOCS, [9] S. Kolliopoulos, C. Stein, Improved approximation algorithms for unsplittable flow problems, Proc. 38th IEEE FOCS, [10] J.K. Lenstra, D. Shmoys, É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Proc. 28th IEEE FOCS, [11] A. Mayer, Y. Ofek, M. Yung, Approximating maxmin fair rates via distributed local scheduling with partial information, Proc. IEEE INFOCOM, [12] N. Megiddo, Optimal flows in networks with sources and sinks, Math Programming 7(1974). [13] S. Plotkin, Competitive Routing in ATM networks, IEEE J. Selected Areas in Communications,
Approximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NPCompleteness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithms
More informationApplied Algorithm Design Lecture 5
Applied Algorithm Design Lecture 5 Pietro Michiardi Eurecom Pietro Michiardi (Eurecom) Applied Algorithm Design Lecture 5 1 / 86 Approximation Algorithms Pietro Michiardi (Eurecom) Applied Algorithm Design
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. #approximation algorithm.
Approximation Algorithms 11 Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of three
More information5.1 Bipartite Matching
CS787: Advanced Algorithms Lecture 5: Applications of Network Flow In the last lecture, we looked at the problem of finding the maximum flow in a graph, and how it can be efficiently solved using the FordFulkerson
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. !approximation algorithm.
Approximation Algorithms Chapter Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of
More informationChapter 11. 11.1 Load Balancing. Approximation Algorithms. Load Balancing. Load Balancing on 2 Machines. Load Balancing: Greedy Scheduling
Approximation Algorithms Chapter Approximation Algorithms Q. Suppose I need to solve an NPhard problem. What should I do? A. Theory says you're unlikely to find a polytime algorithm. Must sacrifice one
More informationThe Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }
More information11. APPROXIMATION ALGORITHMS
11. APPROXIMATION ALGORITHMS load balancing center selection pricing method: vertex cover LP rounding: vertex cover generalized load balancing knapsack problem Lecture slides by Kevin Wayne Copyright 2005
More informationDecentralized Utilitybased Sensor Network Design
Decentralized Utilitybased Sensor Network Design Narayanan Sadagopan and Bhaskar Krishnamachari University of Southern California, Los Angeles, CA 900890781, USA narayans@cs.usc.edu, bkrishna@usc.edu
More informationHow To Solve The Online Advertising Problem
Frequency Capping in Online Advertising Niv Buchbinder Moran Feldman Arpita Ghosh Joseph (Seffi) Naor July 2, 2014 Abstract We study the following online problem. There are n advertisers. Each advertiser
More informationSingle machine parallel batch scheduling with unbounded capacity
Workshop on Combinatorics and Graph Theory 21th, April, 2006 Nankai University Single machine parallel batch scheduling with unbounded capacity Yuan Jinjiang Department of mathematics, Zhengzhou University
More information2.3 Convex Constrained Optimization Problems
42 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Theorem 15 Let f : R n R and h : R R. Consider g(x) = h(f(x)) for all x R n. The function g is convex if either of the following two conditions
More informationCMSC 858T: Randomized Algorithms Spring 2003 Handout 8: The Local Lemma
CMSC 858T: Randomized Algorithms Spring 2003 Handout 8: The Local Lemma Please Note: The references at the end are given for extra reading if you are interested in exploring these ideas further. You are
More informationPermutation Betting Markets: Singleton Betting with Extra Information
Permutation Betting Markets: Singleton Betting with Extra Information Mohammad Ghodsi Sharif University of Technology ghodsi@sharif.edu Hamid Mahini Sharif University of Technology mahini@ce.sharif.edu
More informationImproved Algorithms for Data Migration
Improved Algorithms for Data Migration Samir Khuller 1, YooAh Kim, and Azarakhsh Malekian 1 Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported by NSF Award
More informationJUSTINTIME SCHEDULING WITH PERIODIC TIME SLOTS. Received December May 12, 2003; revised February 5, 2004
Scientiae Mathematicae Japonicae Online, Vol. 10, (2004), 431 437 431 JUSTINTIME SCHEDULING WITH PERIODIC TIME SLOTS Ondřej Čepeka and Shao Chin Sung b Received December May 12, 2003; revised February
More informationNear Optimal Solutions
Near Optimal Solutions Many important optimization problems are lacking efficient solutions. NPComplete problems unlikely to have polynomial time solutions. Good heuristics important for such problems.
More informationScheduling Realtime Tasks: Algorithms and Complexity
Scheduling Realtime Tasks: Algorithms and Complexity Sanjoy Baruah The University of North Carolina at Chapel Hill Email: baruah@cs.unc.edu Joël Goossens Université Libre de Bruxelles Email: joel.goossens@ulb.ac.be
More information8.1 Min Degree Spanning Tree
CS880: Approximations Algorithms Scribe: Siddharth Barman Lecturer: Shuchi Chawla Topic: Min Degree Spanning Tree Date: 02/15/07 In this lecture we give a local search based algorithm for the Min Degree
More informationTwo Algorithms for the StudentProject Allocation Problem
Two Algorithms for the StudentProject Allocation Problem David J. Abraham 1, Robert W. Irving 2, and David F. Manlove 2 1 Computer Science Department, CarnegieMellon University, 5000 Forbes Ave, Pittsburgh
More informationMechanisms for Fair Attribution
Mechanisms for Fair Attribution Eric Balkanski Yaron Singer Abstract We propose a new framework for optimization under fairness constraints. The problems we consider model procurement where the goal is
More informationarxiv:1112.0829v1 [math.pr] 5 Dec 2011
How Not to Win a Million Dollars: A Counterexample to a Conjecture of L. Breiman Thomas P. Hayes arxiv:1112.0829v1 [math.pr] 5 Dec 2011 Abstract Consider a gambling game in which we are allowed to repeatedly
More informationAlgorithm Design and Analysis
Algorithm Design and Analysis LECTURE 27 Approximation Algorithms Load Balancing Weighted Vertex Cover Reminder: Fill out SRTEs online Don t forget to click submit Sofya Raskhodnikova 12/6/2011 S. Raskhodnikova;
More informationMinimizing the Number of Machines in a UnitTime Scheduling Problem
Minimizing the Number of Machines in a UnitTime Scheduling Problem Svetlana A. Kravchenko 1 United Institute of Informatics Problems, Surganova St. 6, 220012 Minsk, Belarus kravch@newman.basnet.by Frank
More informationDefinition 11.1. Given a graph G on n vertices, we define the following quantities:
Lecture 11 The Lovász ϑ Function 11.1 Perfect graphs We begin with some background on perfect graphs. graphs. First, we define some quantities on Definition 11.1. Given a graph G on n vertices, we define
More informationOn the TradeOff between Control Plane Load and Data Plane Efficiency in Software Defined Networks
1 Technion  Computer Science Department  Tehnical Report CS010  01 On the TradeOff between Control Plane Load and Data Plane Efficiency in Software Defined Networks Abstract Software Defined Networking
More informationBargaining Solutions in a Social Network
Bargaining Solutions in a Social Network Tanmoy Chakraborty and Michael Kearns Department of Computer and Information Science University of Pennsylvania Abstract. We study the concept of bargaining solutions,
More informationSingleLink Failure Detection in AllOptical Networks Using Monitoring Cycles and Paths
SingleLink Failure Detection in AllOptical Networks Using Monitoring Cycles and Paths Satyajeet S. Ahuja, Srinivasan Ramasubramanian, and Marwan Krunz Department of ECE, University of Arizona, Tucson,
More informationHow To Find An Optimal Search Protocol For An Oblivious Cell
The Conference Call Search Problem in Wireless Networks Leah Epstein 1, and Asaf Levin 2 1 Department of Mathematics, University of Haifa, 31905 Haifa, Israel. lea@math.haifa.ac.il 2 Department of Statistics,
More information24. The Branch and Bound Method
24. The Branch and Bound Method It has serious practical consequences if it is known that a combinatorial problem is NPcomplete. Then one can conclude according to the present state of science that no
More informationAbout the inverse football pool problem for 9 games 1
Seventh International Workshop on Optimal Codes and Related Topics September 61, 013, Albena, Bulgaria pp. 15133 About the inverse football pool problem for 9 games 1 Emil Kolev Tsonka Baicheva Institute
More informationOn the Multiple Unicast Network Coding Conjecture
On the Multiple Unicast Networ Coding Conjecture Michael Langberg Computer Science Division Open University of Israel Raanana 43107, Israel miel@openu.ac.il Muriel Médard Research Laboratory of Electronics
More information5 INTEGER LINEAR PROGRAMMING (ILP) E. Amaldi Fondamenti di R.O. Politecnico di Milano 1
5 INTEGER LINEAR PROGRAMMING (ILP) E. Amaldi Fondamenti di R.O. Politecnico di Milano 1 General Integer Linear Program: (ILP) min c T x Ax b x 0 integer Assumption: A, b integer The integrality condition
More information1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is or
More informationINDISTINGUISHABILITY OF ABSOLUTELY CONTINUOUS AND SINGULAR DISTRIBUTIONS
INDISTINGUISHABILITY OF ABSOLUTELY CONTINUOUS AND SINGULAR DISTRIBUTIONS STEVEN P. LALLEY AND ANDREW NOBEL Abstract. It is shown that there are no consistent decision rules for the hypothesis testing problem
More informationHow Much Can Taxes Help Selfish Routing?
How Much Can Taxes Help Selfish Routing? Richard Cole Yevgeniy Dodis Tim Roughgarden July 28, 25 Abstract We study economic incentives for influencing selfish behavior in networks. We consider a model
More informationCHAPTER II THE LIMIT OF A SEQUENCE OF NUMBERS DEFINITION OF THE NUMBER e.
CHAPTER II THE LIMIT OF A SEQUENCE OF NUMBERS DEFINITION OF THE NUMBER e. This chapter contains the beginnings of the most important, and probably the most subtle, notion in mathematical analysis, i.e.,
More informationTHE SCHEDULING OF MAINTENANCE SERVICE
THE SCHEDULING OF MAINTENANCE SERVICE Shoshana Anily Celia A. Glass Refael Hassin Abstract We study a discrete problem of scheduling activities of several types under the constraint that at most a single
More informationAdaptive Online Gradient Descent
Adaptive Online Gradient Descent Peter L Bartlett Division of Computer Science Department of Statistics UC Berkeley Berkeley, CA 94709 bartlett@csberkeleyedu Elad Hazan IBM Almaden Research Center 650
More informationDiversity Coloring for Distributed Data Storage in Networks 1
Diversity Coloring for Distributed Data Storage in Networks 1 Anxiao (Andrew) Jiang and Jehoshua Bruck California Institute of Technology Pasadena, CA 9115, U.S.A. {jax, bruck}@paradise.caltech.edu Abstract
More informationProximal mapping via network optimization
L. Vandenberghe EE236C (Spring 234) Proximal mapping via network optimization minimum cut and maximum flow problems parametric minimum cut problem application to proximal mapping Introduction this lecture:
More information3. Linear Programming and Polyhedral Combinatorics
Massachusetts Institute of Technology Handout 6 18.433: Combinatorial Optimization February 20th, 2009 Michel X. Goemans 3. Linear Programming and Polyhedral Combinatorics Summary of what was seen in the
More informationClassification  Examples
Lecture 2 Scheduling 1 Classification  Examples 1 r j C max given: n jobs with processing times p 1,...,p n and release dates r 1,...,r n jobs have to be scheduled without preemption on one machine taking
More informationThe Trip Scheduling Problem
The Trip Scheduling Problem Claudia Archetti Department of Quantitative Methods, University of Brescia Contrada Santa Chiara 50, 25122 Brescia, Italy Martin Savelsbergh School of Industrial and Systems
More informationTHE PROBLEM WORMS (1) WORMS (2) THE PROBLEM OF WORM PROPAGATION/PREVENTION THE MINIMUM VERTEX COVER PROBLEM
1 THE PROBLEM OF WORM PROPAGATION/PREVENTION I.E. THE MINIMUM VERTEX COVER PROBLEM Prof. Tiziana Calamoneri Network Algorithms A.y. 2014/15 2 THE PROBLEM WORMS (1)! A computer worm is a standalone malware
More informationOnline and Offline Selling in Limit Order Markets
Online and Offline Selling in Limit Order Markets Kevin L. Chang 1 and Aaron Johnson 2 1 Yahoo Inc. klchang@yahooinc.com 2 Yale University ajohnson@cs.yale.edu Abstract. Completely automated electronic
More informationLecture 4: BK inequality 27th August and 6th September, 2007
CSL866: Percolation and Random Graphs IIT Delhi Amitabha Bagchi Scribe: Arindam Pal Lecture 4: BK inequality 27th August and 6th September, 2007 4. Preliminaries The FKG inequality allows us to lower bound
More informationStochastic Inventory Control
Chapter 3 Stochastic Inventory Control 1 In this chapter, we consider in much greater details certain dynamic inventory control problems of the type already encountered in section 1.3. In addition to the
More informationThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE/ACM TRANSACTIONS ON NETWORKING 1 A Greedy Link Scheduler for Wireless Networks With Gaussian MultipleAccess and Broadcast Channels Arun Sridharan, Student Member, IEEE, C Emre Koksal, Member, IEEE,
More informationNo: 10 04. Bilkent University. Monotonic Extension. Farhad Husseinov. Discussion Papers. Department of Economics
No: 10 04 Bilkent University Monotonic Extension Farhad Husseinov Discussion Papers Department of Economics The Discussion Papers of the Department of Economics are intended to make the initial results
More informationScheduling Single Machine Scheduling. Tim Nieberg
Scheduling Single Machine Scheduling Tim Nieberg Single machine models Observation: for nonpreemptive problems and regular objectives, a sequence in which the jobs are processed is sufficient to describe
More informationCSC 373: Algorithm Design and Analysis Lecture 16
CSC 373: Algorithm Design and Analysis Lecture 16 Allan Borodin February 25, 2013 Some materials are from Stephen Cook s IIT talk and Keven Wayne s slides. 1 / 17 Announcements and Outline Announcements
More informationA Note on Maximum Independent Sets in Rectangle Intersection Graphs
A Note on Maximum Independent Sets in Rectangle Intersection Graphs Timothy M. Chan School of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1, Canada tmchan@uwaterloo.ca September 12,
More informationA Sublinear Bipartiteness Tester for Bounded Degree Graphs
A Sublinear Bipartiteness Tester for Bounded Degree Graphs Oded Goldreich Dana Ron February 5, 1998 Abstract We present a sublineartime algorithm for testing whether a bounded degree graph is bipartite
More informationExponential time algorithms for graph coloring
Exponential time algorithms for graph coloring Uriel Feige Lecture notes, March 14, 2011 1 Introduction Let [n] denote the set {1,..., k}. A klabeling of vertices of a graph G(V, E) is a function V [k].
More informationMapReduce and Distributed Data Analysis. Sergei Vassilvitskii Google Research
MapReduce and Distributed Data Analysis Google Research 1 Dealing With Massive Data 2 2 Dealing With Massive Data Polynomial Memory Sublinear RAM Sketches External Memory Property Testing 3 3 Dealing With
More informationOptimal Index Codes for a Class of Multicast Networks with Receiver Side Information
Optimal Index Codes for a Class of Multicast Networks with Receiver Side Information Lawrence Ong School of Electrical Engineering and Computer Science, The University of Newcastle, Australia Email: lawrence.ong@cantab.net
More informationA Practical Scheme for Wireless Network Operation
A Practical Scheme for Wireless Network Operation Radhika Gowaikar, Amir F. Dana, Babak Hassibi, Michelle Effros June 21, 2004 Abstract In many problems in wireline networks, it is known that achieving
More informationKey words. multiobjective optimization, approximate Pareto set, biobjective shortest path
SMALL APPROXIMATE PARETO SETS FOR BI OBJECTIVE SHORTEST PATHS AND OTHER PROBLEMS ILIAS DIAKONIKOLAS AND MIHALIS YANNAKAKIS Abstract. We investigate the problem of computing a minimum set of solutions that
More informationLecture 7: NPComplete Problems
IAS/PCMI Summer Session 2000 Clay Mathematics Undergraduate Program Basic Course on Computational Complexity Lecture 7: NPComplete Problems David Mix Barrington and Alexis Maciel July 25, 2000 1. Circuit
More informationPermutation Betting Markets: Singleton Betting with Extra Information
Permutation Betting Markets: Singleton Betting with Extra Information Mohammad Ghodsi Sharif University of Technology ghodsi@sharif.edu Hamid Mahini Sharif University of Technology mahini@ce.sharif.edu
More informationNetwork File Storage with Graceful Performance Degradation
Network File Storage with Graceful Performance Degradation ANXIAO (ANDREW) JIANG California Institute of Technology and JEHOSHUA BRUCK California Institute of Technology A file storage scheme is proposed
More informationA simpler and better derandomization of an approximation algorithm for Single Source RentorBuy
A simpler and better derandomization of an approximation algorithm for Single Source RentorBuy David P. Williamson Anke van Zuylen School of Operations Research and Industrial Engineering, Cornell University,
More informationAnalysis of an Artificial Hormone System (Extended abstract)
c 2013. This is the author s version of the work. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purpose or for creating
More informationThe LoadDistance Balancing Problem
The LoadDistance Balancing Problem Edward Bortnikov Samir Khuller Yishay Mansour Joseph (Seffi) Naor Yahoo! Research, Matam Park, Haifa 31905 (Israel) Department of Computer Science, University of Maryland,
More informationScheduling to Minimize Power Consumption using Submodular Functions
Scheduling to Minimize Power Consumption using Submodular Functions Erik D. Demaine MIT edemaine@mit.edu Morteza Zadimoghaddam MIT morteza@mit.edu ABSTRACT We develop logarithmic approximation algorithms
More informationMax Flow, Min Cut, and Matchings (Solution)
Max Flow, Min Cut, and Matchings (Solution) 1. The figure below shows a flow network on which an st flow is shown. The capacity of each edge appears as a label next to the edge, and the numbers in boxes
More informationTriangle deletion. Ernie Croot. February 3, 2010
Triangle deletion Ernie Croot February 3, 2010 1 Introduction The purpose of this note is to give an intuitive outline of the triangle deletion theorem of Ruzsa and Szemerédi, which says that if G = (V,
More informationCSC2420 Fall 2012: Algorithm Design, Analysis and Theory
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory Allan Borodin November 15, 2012; Lecture 10 1 / 27 Randomized online bipartite matching and the adwords problem. We briefly return to online algorithms
More informationMinimal Cost Reconfiguration of Data Placement in a Storage Area Network
Minimal Cost Reconfiguration of Data Placement in a Storage Area Network Hadas Shachnai Gal Tamir Tami Tamir Abstract VideoonDemand (VoD) services require frequent updates in file configuration on the
More informationNotes from Week 1: Algorithms for sequential prediction
CS 683 Learning, Games, and Electronic Markets Spring 2007 Notes from Week 1: Algorithms for sequential prediction Instructor: Robert Kleinberg 2226 Jan 2007 1 Introduction In this course we will be looking
More informationChapter 7. Sealedbid Auctions
Chapter 7 Sealedbid Auctions An auction is a procedure used for selling and buying items by offering them up for bid. Auctions are often used to sell objects that have a variable price (for example oil)
More informationSchool Timetabling in Theory and Practice
School Timetabling in Theory and Practice Irving van Heuven van Staereling VU University, Amsterdam Faculty of Sciences December 24, 2012 Preface At almost every secondary school and university, some
More informationApproximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs
Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs Yong Zhang 1.2, Francis Y.L. Chin 2, and HingFung Ting 2 1 College of Mathematics and Computer Science, Hebei University,
More informationA Nearlinear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints
A Nearlinear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, and Yogish Sabharwal IBM Research  India, New
More informationMaximizing the Spread of Influence through a Social Network
Maximizing the Spread of Influence through a Social Network David Kempe Dept. of Computer Science Cornell University, Ithaca NY kempe@cs.cornell.edu Jon Kleinberg Dept. of Computer Science Cornell University,
More informationUnraveling versus Unraveling: A Memo on Competitive Equilibriums and Trade in Insurance Markets
Unraveling versus Unraveling: A Memo on Competitive Equilibriums and Trade in Insurance Markets Nathaniel Hendren January, 2014 Abstract Both Akerlof (1970) and Rothschild and Stiglitz (1976) show that
More informationSecurityAware Beacon Based Network Monitoring
SecurityAware Beacon Based Network Monitoring Masahiro Sasaki, Liang Zhao, Hiroshi Nagamochi Graduate School of Informatics, Kyoto University, Kyoto, Japan Email: {sasaki, liang, nag}@amp.i.kyotou.ac.jp
More informationData Migration in Heterogeneous Storage Systems
011 31st International Conference on Distributed Computing Systems Data Migration in Heterogeneous Storage Systems Chadi Kari Department of Computer Science and Engineering University of Connecticut Storrs,
More informationPh.D. Thesis. Judit NagyGyörgy. Supervisor: Péter Hajnal Associate Professor
Online algorithms for combinatorial problems Ph.D. Thesis by Judit NagyGyörgy Supervisor: Péter Hajnal Associate Professor Doctoral School in Mathematics and Computer Science University of Szeged Bolyai
More informationGraphs without proper subgraphs of minimum degree 3 and short cycles
Graphs without proper subgraphs of minimum degree 3 and short cycles Lothar Narins, Alexey Pokrovskiy, Tibor Szabó Department of Mathematics, Freie Universität, Berlin, Germany. August 22, 2014 Abstract
More informationNPcomplete? NPhard? Some Foundations of Complexity. Prof. Sven Hartmann Clausthal University of Technology Department of Informatics
NPcomplete? NPhard? Some Foundations of Complexity Prof. Sven Hartmann Clausthal University of Technology Department of Informatics Tractability of Problems Some problems are undecidable: no computer
More informationOffline sorting buffers on Line
Offline sorting buffers on Line Rohit Khandekar 1 and Vinayaka Pandit 2 1 University of Waterloo, ON, Canada. email: rkhandekar@gmail.com 2 IBM India Research Lab, New Delhi. email: pvinayak@in.ibm.com
More informationSome Polynomial Theorems. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 rkennedy@ix.netcom.
Some Polynomial Theorems by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 rkennedy@ix.netcom.com This paper contains a collection of 31 theorems, lemmas,
More informationGENERATING LOWDEGREE 2SPANNERS
SIAM J. COMPUT. c 1998 Society for Industrial and Applied Mathematics Vol. 27, No. 5, pp. 1438 1456, October 1998 013 GENERATING LOWDEGREE 2SPANNERS GUY KORTSARZ AND DAVID PELEG Abstract. A kspanner
More informationOn the independence number of graphs with maximum degree 3
On the independence number of graphs with maximum degree 3 Iyad A. Kanj Fenghui Zhang Abstract Let G be an undirected graph with maximum degree at most 3 such that G does not contain any of the three graphs
More informationScheduling a sequence of tasks with general completion costs
Scheduling a sequence of tasks with general completion costs Francis Sourd CNRSLIP6 4, place Jussieu 75252 Paris Cedex 05, France Francis.Sourd@lip6.fr Abstract Scheduling a sequence of tasks in the acceptation
More informationDuplicating and its Applications in Batch Scheduling
Duplicating and its Applications in Batch Scheduling Yuzhong Zhang 1 Chunsong Bai 1 Shouyang Wang 2 1 College of Operations Research and Management Sciences Qufu Normal University, Shandong 276826, China
More informationCompressing Forwarding Tables for Datacenter Scalability
TECHNICAL REPORT TR1203, TECHNION, ISRAEL 1 Compressing Forwarding Tables for Datacenter Scalability Ori Rottenstreich, Marat Radan, Yuval Cassuto, Isaac Keslassy, Carmi Arad, Tal Mizrahi, Yoram Revah
More informationThe StudentProject Allocation Problem
The StudentProject Allocation Problem David J. Abraham, Robert W. Irving, and David F. Manlove Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, UK Email: {dabraham,rwi,davidm}@dcs.gla.ac.uk.
More informationHow To Solve A Minimum Set Covering Problem (Mcp)
Measuring Rationality with the Minimum Cost of Revealed Preference Violations Mark Dean and Daniel Martin Online Appendices  Not for Publication 1 1 Algorithm for Solving the MASP In this online appendix
More informationCS 3719 (Theory of Computation and Algorithms) Lecture 4
CS 3719 (Theory of Computation and Algorithms) Lecture 4 Antonina Kolokolova January 18, 2012 1 Undecidable languages 1.1 ChurchTuring thesis Let s recap how it all started. In 1990, Hilbert stated a
More informationCompact Representations and Approximations for Compuation in Games
Compact Representations and Approximations for Compuation in Games Kevin Swersky April 23, 2008 Abstract Compact representations have recently been developed as a way of both encoding the strategic interactions
More informationRandomization Approaches for Network Revenue Management with Customer Choice Behavior
Randomization Approaches for Network Revenue Management with Customer Choice Behavior Sumit Kunnumkal Indian School of Business, Gachibowli, Hyderabad, 500032, India sumit kunnumkal@isb.edu March 9, 2011
More informationDiscrete Applied Mathematics. The firefighter problem with more than one firefighter on trees
Discrete Applied Mathematics 161 (2013) 899 908 Contents lists available at SciVerse ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam The firefighter problem with
More informationFACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z
FACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z DANIEL BIRMAJER, JUAN B GIL, AND MICHAEL WEINER Abstract We consider polynomials with integer coefficients and discuss their factorization
More informationCOMBINATORIAL PROPERTIES OF THE HIGMANSIMS GRAPH. 1. Introduction
COMBINATORIAL PROPERTIES OF THE HIGMANSIMS GRAPH ZACHARY ABEL 1. Introduction In this survey we discuss properties of the HigmanSims graph, which has 100 vertices, 1100 edges, and is 22 regular. In fact
More informationDynamic TCP Acknowledgement: Penalizing Long Delays
Dynamic TCP Acknowledgement: Penalizing Long Delays Karousatou Christina Network Algorithms June 8, 2010 Karousatou Christina (Network Algorithms) Dynamic TCP Acknowledgement June 8, 2010 1 / 63 Layout
More informationAn Approximation Algorithm for Bounded Degree Deletion
An Approximation Algorithm for Bounded Degree Deletion Tomáš Ebenlendr Petr Kolman Jiří Sgall Abstract Bounded Degree Deletion is the following generalization of Vertex Cover. Given an undirected graph
More informationIntegrating Benders decomposition within Constraint Programming
Integrating Benders decomposition within Constraint Programming Hadrien Cambazard, Narendra Jussien email: {hcambaza,jussien}@emn.fr École des Mines de Nantes, LINA CNRS FRE 2729 4 rue Alfred Kastler BP
More information