arXiv CSopen access

A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput

arXiv:2605.04699v1 [cs.NI] 6 May 2026

A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput Matthias Bentert1 , Chen Avin2 , and Stefan Schmid1 1

2

Technische Universität Berlin, Germany Ben-Gurion University of the Negev, School of Electrical and Computer Engineering, Israel

Abstract The performance of distributed applications often critically depends on the interconnecting network or more specifically on its throughput: how fast data can be carried across a network. Over the last years, great progress has been made in understanding demand-oblivious throughput: how fast a given demand matrix describing pairwise communication requirements, can be served on a given network. However, surprisingly little is known today about the achievable demand-aware throughput: the throughput on a network topology which can be optimized toward the demand. Such demand-aware networks have recently gained popularity in datacenters and are enabled by emerging reconfigurable optical technologies. In this paper, we are interested in both the achievable demand-aware throughput bounds as well as in the computational complexity of finding a throughput-optimizing network topology. We take a systematic approach and investigate four variants of demand-aware throughput: we analyze, and derive bounds for, two definitions of throughput, the classic throughput usually considered in the literature, and a new generalized definition which we call weak throughput; for each of them, we consider two routing models, a direct one where demand can only be served on a single hop and a general one where multi-hop routing is allowed. Our main result is a separation result which solves an open problem in the literature about the classical throughput definition, showing that demand-aware topologies can outperform demand-oblivious topologies even in the worst case: the demandaware throughput asymptotically approaches at least 58 , while it is known that the n demand-oblivious throughput is at most 2n−1 ≈ 12 . In terms of computational complexity, we show that computing the demand-aware weak throughput is NP-hard, but computing the demand-aware direct throughput and the demand-aware weak direct throughput are both polynomial-time solvable. We leave it as an open problem whether computing the demand-aware throughput is polynomial-time solvable or NP-hard, but we conjecture that it is NP-hard.

1

1

Introduction

Many data-intensive distributed applications, especially those related to high-performance computing and machine learning, critically depend on a high-throughput interconnecting communication network. Accordingly, over the last decades, significant efforts have been made to design novel datacenter networks which provide high capacity at low cost. To this end, researchers intensively studied how to define and measure the throughput of a network [23, 29], how to model its impact on application performance [13, 27], and how to improve it [2, 5, 6, 11, 25, 26, 32]. A particularly intriguing solution are demand-aware networks (also known as topology engineering in the literature) [7, 8, 9, 10, 14, 18, 20, 31, 34]: networks whose topology can be optimized towards the demand using emerging optical switching technologies. However, defining and analyzing the throughput of a demand-aware network topology is surprisingly subtle. Existing literature so far mostly revolves around the demand-oblivious throughput: design a network topology (a graph) G (with given link capacities) that can serve well any (doubly stochastic) demand matrix M, describing pairwise communication requirements. More specifically, the throughput of a (directed) graph G with respect to a demand matrix M is defined by the maximum factor by which the rates specified in the demand matrix must be scaled (or equivalently, the time horizon of the transmission increased) such that they can be served on the topology without violating its link capacities [1, 2, 20, 22, 23, 24, 33, 34]. The throughput of a graph is defined as its worst-case throughput over all possible demand matrices. It is already known that the throughput of n ≈ 21 [24]. Empirical studies demand-oblivious networks connecting n nodes is at most 2n−1 suggest that demand-aware networks can achieve a higher throughput. However, whether this also holds under worst-case demand matrices has been an open question for several years [1, 2, 15, 20]. We study this fundamental question. Particularly: is there a separation between the worst case demand-aware throughput and the demand-oblivious throughput? To shed light on the demand-aware throughput, we take a systematic approach and study both the achievable bounds as well as the computational complexity of optimizing the topology. Moreover, we consider two different throughput definitions and two different routing models, that is, four scenarios in total. In particular, in addition to the classic throughput definition in the literature mentioned above, we also introduce an intuitive and more general definition which we call the weak throughput of a network: in a nutshell (details will follow), the weak throughput measures the highest possible percentage of demands that can be served. In terms of routing models, we consider a multi-hop scenario, where the demand can be routed arbitrarily over the network, and a single-hop scenario, where the demand can be served only across a single link—as is sometimes the case in optical networks [21]. We refer to the latter as direct routing. Before presenting our contributions in detail, we introduce our model more formally.

2

1.1

Formal Model

For a positive integer n, we use [n] to denote the set {1, 2, . . . , n}. We use 1x for a Boolean expression x as the indicator function: “1 if x holds and 0 otherwise”. For a sequence σ = (ϕ1 , ϕ2 , . . . , ϕℓ ), we use x ∈ σ as a shorthand for x ∈ {ϕ1 , ϕ2 , . . . , ϕℓ }. We model networks as multigraphs, that is, graphs can contain self-loops and parallel arcs. If each vertex in a directed graph G has exactly r incoming and outgoing arcs, then we call G a directed r-regular graph. A path P in a directed graph is a sequence of arcs ((u1 , v1 ), (u2 , v2 ), . . . , (uℓ , vℓ )) such that for all i ∈ [ℓ − 1] it holds that vi = ui+1 . We say that P is a path from u1 to vℓ . The length len(P ) = ℓ of a path P is the number of arcs in it and we only consider paths containing at least one arc in this work. This is consistent with the existing literature, where demand from a node v to itself has to use some arcs (possibly a self-loop). We mention in passing that while our specific constructions do use self-loops, all of our results can also be transferred to the setting where demand from a node to itself can be served by empty paths. The throughput bounds (and a construction in a hardness proof later on) will then of course be slightly different. A matrix is doubly stochastic if each entry is non-negative and each row and each column sums to 1. As in the existing literature, we will assume that all input matrices are doubly stochastic. For a matrix M = (ai,j )i,j∈[n] and a number x, we use xM to denote the matrix, where each entry is scaled by a factor of x, that is, the matrix (xai,j )i,j∈[n] . We will often match the i-th row and i-th column of a matrix to the i-th vertex in a graph. For notational convenience, we will often use [n] as the set of vertices to easily index the rows and columns of the matrix with the names of the vertices. Given a matrix M = (ai,j )i,j∈[n] and a directed graph G with arc capacities where the sum of capacities entering and leaving each vertex is 1, we say that G can host M if there is a flow (a collection P = {(P1 , d1 ), (P2 , d2 ), . . . , (Pℓ , dℓ )} of ℓ pairs—where each Pi is a directed (non-empty) path in G from some vertex si to some (not necessarily different) vertex ti and di is a number) such that P is a multi-commodity flow in G satisfying the demand requirements of M and not violating the capacities of G. If the graph is r-regular and each arc has capacity 1r , then this is equivalent to setting each capacity to 1 and requiring that G can satisfy the multicommodity flow described by rM. More formally, the following holds. P • For all (u, v) ∈ V × V , i∈[ℓ] (di · 1si =u · 1ti =v ) = r · au,v and P • for all arcs e = (u, v) in G, it holds that i∈[ℓ] (1e∈Pi · di ) ≤ 1. We say that G can directly host M if G can host M in such a way that all paths in P only consist of a single arc each. The throughput of G with respect to M is the largest number θ such that G can host the matrix θM and the direct throughput of G with respect to M is the largest number θ′ such that G can directly host the matrix θ′ M.1 1

There also exist cut-based measures to capture the throughput or “capacity of a network” in the literature [3, 5, 12, 19]. However, these have shown to be suboptimal [23, 29, 33] and have become less popular recently.

3

The weak throughput of G with respect to M is the largest number P η such ′that G can host ai,j ′ ′ ′ a matrix M = (ai,j )i,j∈[n] where ai,j ≤ ai,j for all i, j ∈ [n] and P(i,j)∈V ×V ai,j = η. We also (i,j)∈V ×V say that G can host an η-fraction of M. Note that since we assume that P the input matrix a′ is doubly stochastic, the weak throughput can equivalently be defined by (i,j)∈Vn ×V i,j = η. Finally, the direct weak throughput of G with respect to M is the largest number η such that G can directly host an η-fraction of M and the (weak) throughput of a graph is the smallest throughput of G for any (doubly stochastic) demand matrix M. Keslassy, Chang, McKeown, and Lee showed the following result on the optimal demandoblivious throughput.2 They provided a certain graph for each number n of nodes that n n achieves a throughput of 2n−1 and showed that no other graph has throughput at least 2n−1 . Theorem 1 ([24, Theorem 9]). For each positive integer n, there exists a directed graph Gn n with n vertices such that for any n × n demand matrix M, Gn achieves throughput 2n−1 for M. For any graph G with n vertices and any ε > 0, there exists a matrix MG,ε such n + ε for MG,ε . that G does not achieve throughput 2n−1 Our paper is motivated by two fundamental questions. First, can these bounds be improved in demand-aware networks, that is, if we are allowed to chose the graph after knowing the input matrix, and second, what is the computational complexity for computing a graph maximizing (weak) throughput. As it is common in the related literature in the real of demand-aware networks (but not in the realm of demand-oblivious throughput), we require that all arcs have the same capacity. This also means that there is a fixed number N of arcs entering and leaving any given node. The (unique) optimal demandoblivious construction turned out to have N = 2n − 1 and to make a meaningful separation from the demand-oblivious case, we decided to also pick N = 2n − 1 for the demand-aware case. This is allows us to state the four computational problems we study in this work: Demand-Aware Throughput Input: A doubly stochastic demand matrix M and a number 0 ≤ κ ≤ 1. Question: Is there a directed (2n − 1)-regular graph G such that the throughput of G with respect to M is at least κ? Demand-Aware Weak Throughput Input: A doubly stochastic demand matrix M and a number 0 ≤ κ ≤ 1. Question: Is there a directed (2n − 1)-regular graph G such that the weak throughput of G with respect to M is at least κ? Demand-Aware Direct Throughput Input: A doubly stochastic demand matrix M and a number 0 ≤ κ ≤ 1. Question: Is there a directed (2n−1)-regular graph G such that the direct throughput of G with respect to M is at least κ? 2

Recently, similar results have also been obtained for dynamic settings [1, 6, 24, 29].

4

Table 1: Lower and upper bounds for the different notions of demand-aware throughput we consider in this paper. An entry A / B means a lower bound of A and an upper bound of B. The variable ε stands for an arbitrarily small positive constant. The entries marked with † only hold for n = 2 and the entries marked with ‡ only hold for a sufficiently large number n of nodes. demand aware

throughput

general

5 − ε‡ 8

direct

n 2n−1

/ 56 †

n / 2n−1

weak

/ 89 † 7n−4 7n−3 / 8n−4 8n−4 7n−4 8n−4

Demand-Aware Weak Direct Throughput Input: A doubly stochastic demand matrix M and a number 0 ≤ κ ≤ 1. Question: Is there a directed (2n−1)-regular graph G such that the direct throughput of G with respect to M is at least κ?

1.2

Our Contribution

We contribute fundamental insights into the achievable throughput bounds of demandaware networks and the underlying computational complexities. The main finding of our work is a separation result, solving the open problem whether demand-awareness can improve the throughput also in the worst case. Specifically (more formally stated and proven as Theorem 5 later): Theorem 2. For each ε > 0, there exists an integer nε such that for each n ≥ nε and each n × n demand matrix M, there exists a graph G that achieves a throughput of 85 − ε for M. More systematically, we show lower and upper bounds for all four problem variants we consider. The results are shown in Table 1. To the best of our knowledge, weak throughput has only been considered implicitly in the literature before [23] and we are not aware of any formal definitions and guarantees. Our bounds for Demand-Aware Direct Throughput and Demand-Aware Weak Direct Throughput are essentially tight, whereas there are still gaps for Demand-Aware Throughput and Demand-Aware Weak Throughput. We also study the computational complexity of all four variants (depicted in Table 2) and show that both direct versions can be computed in polynomial time. Regarding the multi-hop setting, we show that the demand-aware weak throughput is NP-hard to compute and the complexity of computing the demand-aware throughput remains an interesting open problem. We mention that while polynomial-time algorithms for the exact weak throughput are impossible assuming P ̸= NP, the lower bound listed in Table 1 is constructive and a graph achieving this bounds can be computed in polynomial time. 5

Table 2: The computational complexity of the different demand-aware throughput notions we consider.

1.3

demand aware

throughput

weak

general

open

NP-hard

direct

O(n3 )

O(n4 log(n))

Our Methods

We next give a high-level overview of how the different results are achieved. We start with the algorithms. The optimal algorithm for Demand-Aware Direct Throughput is a simple greedy algorithm and the argument why it is optimal also gives the tight lower bound. The optimal algorithm for Demand-Aware Weak Direct Throughput is a reduction to maximum-cost flow. The NP-hardness for Demand-Aware Weak Throughput is shown via an intricate reduction from Exact Cover by 3-Sets. On a very high level, there is a vertex for each element and a gadget for each set in the original instance. For each set gadget, there are two optimal solutions locally and we ensure that one of them can be used at most N3 times, where N is the number of elements in the original instance. This solution also allows all nodes corresponding to elements in the respective set to fulfill a tiny bit of additional demand. The value κ is then chosen such that all such nodes need to fulfill this additional demand and hence any solution needs to pick N3 sets that together contain all N elements, that is, they form an exact cover. We continue with the lower and upper bounds, but we mention that all upper bounds are shown by constructing explicit (relatively simple) counterexamples and hence there is not much to say about them. The lower bound for Demand-Aware Direct Throughput follows from the greedy algorithm mentioned above. Our main result is the lower bound for Demand-Aware Throughput. This result builds upon two results that were previously used in approximation algorithms. The first is called dependent rounding and gives a randomized algorithm for a certain matrix-rounding problem. The second result allows to apply Chernoff-type bounds in a setting with variables that are not independent but dependent in a particular way which appears in the context of dependent rounding. In a nutshell, we use half of the arcs in a demand-aware manner using dependent rounding to greedily satisfy a large fraction of the demands directly. The other half of the arcs are placed in a demand-oblivious manner. We then send a certain fraction of the demands originating in any given vertex directly and therein mostly use the demand-aware arcs but potentially also some of the capacity of any demand-oblivious arc. The dependent rounding ensures that the expected amount for any such arc is somewhat small and using the probabilistic method and the probability analysis mentioned above, we are able to show that for a sufficiently large number of nodes, some rounding must exist where the sum of capacities of the demand-oblivious arcs entering or leaving any particular vertex is − ε. These capacities then allow us to send all remaining demands via paths of at least 3n 4 6

weak throughput throughput

weak direct throughput

direct throughput Figure 1: Relations of different demand-aware throughput notions. An arrow from a notion A to a notion B indicates that A ≥ B for all demand matrices. length two using an adaptation of the demand-oblivious routing scheme. In particular, for each pair (vi , vj ) of nodes, we send demand from vi to vj via any given node vh which is proportional to min(c(i, h), c(h, j)), where c(a, b) is the remaining capacity of the demand oblivious arc from va to vb . The last result is an lower bound for Demand-Aware Weak Direct Throughput (which is also a lower bound for Demand-Aware Weak Throughput). Here, we first show that given any matrix where all entries are between 0 and 1 and each row and column sums to an integer, there is a way to round all entries to 0 or 1 such that the sum in each row and column remains the same and the average entry rounded up is at least as large as the average entry in the entire matrix. Them we use this result for the lower bound as follows. We first greedily place arcs whose full capacity can be used to serve demand directly. Then, we use the above rounding to ensure that from the remaining demand, we can satisfy at least the average remaining demand times the number of remaining arcs to . be placed. We also show that this gives a lower bound of 7n−4 8n−4 The rest of the paper is structured as follows. We first show in Section 2 how the different throughput notions relate to one another. Section 3 is devoted to showing our upper and lower bounds for Demand-Aware Throughput and Demand-Aware Direct Throughput. Our upper and lower bounds for Demand-Aware Weak Throughput and Demand-Aware Weak Direct Throughput are shown in Section 4 and our algorithms and the NP-hardness result are proven in Section 5. We conclude with Section 6.

2

Relations Between Different Throughput Notions

We first investigate how the different throughput notions relate to each other. Our findings are summarized in Figure 1. Note that any single arc also describes a non-empty path. This simple observation yields the following. Observation 1. Let M be a doubly-stochastic n × n matrix and κ ∈ [0, 1]. If (M, κ) is a yes-instance of Demand-Aware Direct Throughput, then it is also a yes-instance of Demand-Aware Throughput. Furthermore, if (M, κ) is a yes-instance of DemandAware Weak Direct Throughput, then it is also a yes-instance of Demand-Aware Weak Throughput. Next, we show that the weak (direct) throughput gives an upper bound for the (direct) 7

throughput. To this end, consider any instance (M, κ) of Demand-Aware Throughput or Demand-Aware Direct Throughput, where M = (ai,j )i,j∈[n] . . As each row of the resulting Let a′i,j = κai,j . Since 0 ≤ κ ≤ 1, it holds that a′i,j ≤ ai,jP a′

matrix M′ sums to κ and there are n rows, it holds that i,j∈Vn×V i,j = nκ = κ, that is, n (M, κ) is a yes-instance of Demand-Aware Weak Throughput or Demand-Aware Weak Direct Throughput, respectively. This yields the following. Observation 2. Let M be a doubly-stochastic n × n matrix and κ ∈ [0, 1]. If (M, κ) is a yes-instance of Demand-Aware Throughput, then it is also a yes-instance of Demand-Aware Weak Throughput. Furthermore, if (M, κ) is a yes-instance of Demand-Aware Direct Throughput, then it is also a yes-instance of Demand-Aware Weak Direct Throughput. Given the above results, one might now wonder whether there is also a similar connection between the demand-aware throughput and the demand-aware weak direct throughput. We next show that this is not the case. Consider the matrices 9 1 1 1 2 2 10 . M1 = 1 1 and M2 = 10 9 1 2

2

10

10

The optimal networks for M1 and M2 for the demand-aware throughput and the demandaware weak direct throughput are shown in Figure 2. On the one hand, it holds that (M1 , 98 ) is a yes-instance of Demand-Aware Throughput and a no-instance of DemandAware Weak Direct Throughput (since the highest weak direct throughput that is 9 ) is a yes-instance of Demand-Aware achievable for M1 is 56 ). On the other hand, (M2 , 10 Weak Direct Throughput, but a no-instance of Demand-Aware Throughput (as 9 the highest achievable throughput for M2 is 100 < 10 ). 114 To conclude this section, we observe that since the graph G behind Theorem 1 is (2n−1)regular, it holds that the demand-aware throughput for any demand matrix is at least as much as the one achieved by G, that is, the demand-aware throughput is at least as good as the demand-oblivious throughput (where no restriction is made on the number of arcs in G other than that the sum of capacities outgoing and incoming to each node is 1). n Observation 3. For any doubly-stochastic n × n demand matrix M and any κ ≤ 2n−1 , it holds that (M, κ) is a yes-instance of Demand-Aware Throughput.

3

Throughput Bounds

In this section, we show lower and upper bounds for the demand-aware (direct) throughput. We start with a lower bound of 85 − ε for throughput for any ε > 0 that relies on the probabilistic method. Therein, we rely on randomized techniques previously applied in the context of approximation algorithms. However, our final result will be a deterministic lower bound. Afterwards, we investigate demand-aware direct throughput and show that a direct n throughput of 2n−1 is always achievable and this bound is tight, that is, for any ε > 0, n there exist matrices such that a throughput of 2n−1 + ε is unobtainable. 8

1

2

1

(a) The graph optimizing throughput for M1 . Note that for κ = 89 , we can use the capacity of 32 from vertex 1 to vertex 2 to send a flow of 94 directly and to send twice a flow of 19 from 1 to 2 (once to start a flow which is then sent back to vertex 1 and once to complete a symmetric flow starting in vertex 2). The flow from vertex 1 to itself is then 13 + 91 = 49 and all arc capacities are fully saturated.

1

2

(b) The graph optimizing throughput for M2 . Note that for κ = 100 114 , we can use the capacity of 13 from vertex 1 to vertex 2 10 to send a flow of 114 directly and to send 14 twice a flow of 114 from 1 to 2 (once for flow from 1 to 1 and once for flow from 2 to 2). The flow from vertex 1 to itself 14 90 9 = 2·38+14 = 114 = 100 is then 23 + 114 114 114 · 10 and all arc capacities are fully saturated 38 since 10+2·14 = 114 = 31 . 114

2 1

1

2

2

(c) The graphs optimizing weak direct throughput for M1 . Note that in both cases each node can satisfy a flow of 21 to one of the two vertices and a flow of 13 to the other, that is 56 in total.

(d) The graph optimizing weak direct throughput for M2 . Note that each node can satisfy 0.9 of the demand originating in it, that is, the weak direct throughput 9 is (at least) 10 .

Figure 2: The directed 3-regular and the weak direct  graphs  optimizingthe throughput  throughput for matrices M1 =

3.1

1 2 1 2

1 2 1 2

and M2 =

9 10 1 10

1 10 9 10

.

Throughput

We will next prove a lower and an upper bound for the demand-aware throughput of networks. We start with the lower bound. Therein, we make use the following result due to Gandhi et al. [16, Theorem 2.3].3 Theorem 3. Given a matrix M = (αi,j )i,j∈[n] where each entry is between 0 and 1 and each row and each column sums to an integer value, there is a rounding scheme creating a matrix N = (βi,j )i,j∈[n] where βi,j ∈ {0, 1} and 1. βi,j = 1 with probability (exactly) αi,j , 3

We slightly reformulated the statement to fit our notation. The authors of the original result interpret any n × m matrix as the adjacency matrix of a biparitite graph with n vertices on one side and m vertices on the other side. We only require the special case where n = m and statement (P3) of the original paper only for the case b = 0.

9

2. the sum of entries in N in any row or column is the same as the corresponding sum in M (with probability 1), 3. for all i ∈ Q[n] and for any subset S ⊆ [n], the probability that βi,j = 0 for all j ∈ S is at most j∈S (1 − αi,j ), and 4. for all j Q ∈ [n] and for any subset S ⊆ [n], the probability that βi,j = 0 for all i ∈ S is at most i∈S (1 − αi,j ). We also use a result due to Panconesi and Srinivasan [30] (in a reformulation due to Gandhi et al. [16, Theorem 3.1]). Intuitively, this can be thought of as a guarantee that the rounding from the previous result does not deviate from the expected value by more than an ε-fraction in any row or column. A little more formally, it bounds the probability that the sum of entries in a given row or column is at most (1 − δ)µ for any given δ > 0, where µ is the expected sum in that row or column. Theorem 4. Let 0 ≤ a1 , a2 , . . . , at , x1 , x2 , . . . , xt ≤ 1, let X1 , XP 2 , . . . , Xt ∈ {0, 1} be random variables, where Xi = 1 has probability xi , and let µ = i∈[t] ai xi be the expected P value of i∈[t] ai Xi . Suppose for all S ⊆ [t], it holds that the probability that Xi = 0 for Q all i ∈ S is at most i∈S (1 − xi ). Then, for any δ ∈ [0, 1], it holds that the probability P µδ 2 that i∈[t] ai Xi ≤ µ(1 − δ) is at most e− 2 . We can now show our main result. Theorem 5. For each κ < 58 , there exists an integer nκ such that for all n ≥ nκ and each doubly stochastic n × n matrix M, the instance (M, κ) is a yes-instance of DemandAware Throughput. 1 1 n as otherwise κ ≤ 21 + 4n−2 = 2n−1 Proof. Let ε = κ − 58 > 0. We assume that ε < 18 − 4n−2 and Theorem 1 shows that (M, κ) is a yes-instance of Demand-Aware Throughput. Moreover, it holds that (2n − 1)κ > n − 1. Let nκ be the smallest positive integer such 2ε2 nκ

1 6 that nκ ≥ 16ε + 1 and e− 3 < 2n1κ . Note that such a number always exists as e−xn < yn holds for any pair x, y > 0 for all sufficiently large n. Let M = (ai,j )i,j∈[n] be any doubly stochastic n × n matrix with n ≥ nκ . We will show that (M, κ) is a yes-instance of Demand-Aware Throughput. Let bi,j = (n−1)ai,j and b′i,j = bi,j −⌊bi,j ⌋ for all i, j ∈ [n]. Recall that (2n − 1)κ > n − 1. Hence, bi,j < (2n − 1)κai,j . We will employ a randomized rounding technique (based on Theorem 3) and fix the rounding later. For now, let Xi,j be a random variable that takes values in {0, 1} where Xi,j = 1 corresponds to rounding entry bi,j up and otherwise bi,j is rounded down. The probability that Xi,j = 1 is b′i,j . Now, consider any rounding φ of the matrix N ′ = (b′i,j )i,j∈[n] that Theorem 3 could return and let ci,j ∈ {⌊bi,j ⌋, ⌈bi,j ⌉} be the result of applying the same rounding to bi,j . Let di,j = ci,j + 1 > bi,j . Note that Pdue to property (2) in Theorem 3, each row i in the matrix N = (di,j )i,j∈[n] sums to nj=1 (bi,j + 1) = (n − 1) + n = 2n − 1 and the same holds for each column j.

10



3 8 3 M = (ai,j )i,j∈[3] =  8 1 4



75 64  75 (2n − 1)κM =  64 25 32

1 4 3 8 3 8 25 32 75 64 75 64









3 3 8 4   3 1 (n − 1)M = (b ) =   i,j i,j∈[3] 4 4 3 1 8 2 75 64 25  32  75 64

1 2 3 4 3 4



3 4 1 2 3 4

 1 0 1   rounding (ci,j )i,j∈[3] = 1 1 0 0 1 1 

  9 27 27 2 1 2 64 32 64    27 9  (di,j )i,j∈[3] = 2 2 1 overflow (σi,j )i,j∈[3] =  27 64 64 32    9 27 27 = (ci,j + 1)i,j∈[3] 1 2 2 = (2n − 1)κai,j − bi,j 32 64 64 i,j∈[3]     1 1 2 1 2 2 25     excess capacity (ηi,j )i,j∈[3] =  1 1 21  common excess (ζi,j )i,j∈[3] =  52 2 2     P 1 2 52 2 1 1= = min(di,j − bi,j , 1) 2 h∈[n] min(ηi,h , ηh,j ) 

i,j∈[3]

i,j∈[3]

Figure 3: An example of our approach for the second stage for κ = 58 (that is, ε = 0) and n = 3. We mention that the approach does not work as ε does not satisfy the two conditions we have for it. We still chose ε = 0 for the sake of clarity of presentation of the example. We will now construct the graph that can host κM and for notational convenience, we will consider the names of the vertices in it 1, 2, . . . , n. For a given rounding φ and any i, j ∈ [n], we add di,j arcs from vertex i to vertex j. Note that this can be seen as adding ci,j demand-aware arcs and one additional demand-oblivious arc between each pair of (not necessarily distinct) vertices. We partition the flow into two parts and describe them in two separate stages. In the first stage, we send bi,j < min(ai,j , di,j ) demand from vertex i to vertex j directly, that is, we add the pair (((i, j)), bi,j ) to the solution collection P. For the second stage, we introduce some additional notation. See Figure 3 for an example instance with all of the following definitions. Let ηi,j = min(di,j − bi,j , 1) be the excess capacity from vertex i to vertex j. Note that at least ηi,j capacity is not used so far on the arcs going from vertex i to vertex j. The expected excess capacity is b′i,j · 1 + (1 − b′i,j ) · (1 − b′i,j ) = (b′i,j )2 − b′i,j + 1 ≥ 34 . Here, the last inequality holds because the derivative of f (x) = x2 − x + 1 is 2x − 1, which evaluates to 0 at x = 12 , which is also the minimum entry for f and f ( 12 ) = 34 . By the linearity of the expectation, the expected sum of excess in a single row or column is at least 3n . 4 We will next prove that the probability that the excess capacity in any fixed row or 1 column is at most ( 34 − ε)n is smaller than 2n . Since the argument is completely symmetric for rows and P columns, we will only show it for a fixed row. To this end, fix any row i and and let Yi = j∈[n] (1 − b′i,j ). Note that the sum of excess capacities in row i is at least Yi . P More precisely, it is Yi + j∈[n] Xi,j b′i,j . Applying Theorem 4 with t = n + Yi , aj = b′i,j = xj 11

for all j ∈ [n], aj = 1 = xj for all j ∈ {n + 1, n + 2, . . . , n + Yi }, and δ = 4ε yields that the 3 3n δ 2 4

probability that the excess capacity in row i is at most 3n (1 − δ) is at most e− 2 . Note 4 3n 3n 3 3 that 4 (1 − δ) = 4 − 4 δn = ( 4 − ε)n. Thus, the probability that the excess capacity in 3n δ 2 4

3

4

2

2

2

1 . row i is at most ( 34 − ε)n is at most e− 2 = e− 8 n( 3 ε) = e− 3 nε < 2n We are now in a position to fix the specific rounding. To this end, we say that a rounding is good for a certain row or column, if the sum of excess capacities in that row/column is at least ( 34 − ε)n. The probability that a random rounding is good for a given row or 1 as proven above. The probability that any given rounding is column is larger than 1 − 2n x . This is true since even in the good for x fixed rows and/or columns is larger than 1 − 2n worst case bad events can be at most disjoint and the likelihood of at least one of them happening is at most the sum of their individual probabilities. Hence, the probability that = 0. Thus, the a rounding is good for all n rows and all n columns is larger than 1 − 2n 2n probability is strictly larger than 0 and thus such a rounding necessarily exists (but we do not know how to compute it). We consider φ to be such a rounding for the rest of the proof. Now that we fixed the rounding, it remains to prove that the constructed graph can host the matrix κM. To this end, we already showed that bi,j flow can be sent from vertex i to vertex j directly without using any excess capacity. We next show that all remaining flow can be satisfied using only the excess capacities and paths of length P two. To this end, we first define the common excess of row i and column j as ζi,j = h∈[n] min(ηi,h , ηh,j ). Since 0 ≤ ηa,b ≤ 1 for all a, b ∈ [n] and the excess capacity of each row and column is at least ( 43 − ε)n, it holds that ζi,j ≥ ( 21 − 2ε)n. This is true since all ηi,h and ηh,j being 1 results in ζi,j = n and reducing any entry by an amount δ can reduce ζi,j by at most δ. Since the total reduction in row i is at most ( 14 + ε)n and the total reduction in column j is at most ( 41 + ε)n, it holds that ζi,j ≥ n − 2( 41 + ε)n = ( 12 − 2ε)n. Next, let σi,j = ((2n − 1)κ − (n − 1))ai,j for each i, j ∈ [n] be the overflow from i to j. Note that we already saturated bi,j = (n − 1)ai,j flow directly and hence the overflow describes exactly the amount of flow that still needs to be scheduled. For each i, j, h ∈ [n], min(ηi,h ,ηh,j ) flow over arcs (i, h) and (h, j), that is, we add the pairs we send σi,j · ζi,j

(P = ((i, h), (h, j)), σi,j ·

min(ηi,h , ηh,j ) ) ζi,j

to the solution collection P of flows. To conclude the proof, we will show that σi,j flow is sent from i to j in this way and that from any vertex a to any vertex b, at most the excess capacity for this pair is used for all of these P flows combined. For the first point, note that ζi,j = h∈[n] min(ηi,h , ηh,j ) by definition. Thus, X h∈[n]

σi,j ·

σi,j X min(ηi,h , ηh,j ) σi,j ζi,j = min(ηi,h , ηh,j ) = = σi,j . ζi,j ζi,j ζi,j h∈[n]

This shows that all overflow is sent from i to j in this manner. 12

For the second point, recall that ζi,j ≥ ( 12 − 2ε)n for all i, j ∈ [n]. Moreover, note that the sum of overflows originating from i is X X σi,j = ((2n − 1)κ − (n − 1))ai,j j∈[n]

j∈[n]

= (2n − 1)κ − (n − 1)

X

ai,j = (2n − 1)κ − (n − 1).

j∈[n]

P Similarly,the sum of overflows terminating in j is i∈[n] σi,j = (2n − 1)κ − (n − 1). Any arc (a, b) is only used for two types of flows in the second step: overflow terminating in vertex b and overflow originating from vertex a. Thus, the maximum flow sent over the arc(s) (a, b) in the second step is at most X min(ηa,b , ηb,j ) min(ηi,a , ηa,b ) )+ (σa,j ) ζi,b ζa,j j∈[n] i∈[n] X X ηa,b ηa,b )+ (σa,j 1 ) ≤ (σi,b 1 ( 2 − 2ε)n ( 2 − 2ε)n X

(σi,b

j∈[n]

i∈[n]

≤ ηa,b

2((2n − 1)κ − (n − 1)) ( 12 − 2ε)n

≤ ηa,b

2((2n − 1)( 85 − ε) − (n − 1)) ( 21 − 2ε)n

≤ ηa,b

− 2nε − 58 + ε − (n − 1)) 2( 10n 8 ( 12 − 2ε)n n

≤ ηa,b 2

− 4nε + 86 + 2ε ( 12 − 2ε)n

( 12 − 2ε)n − 2nε + 43 + 2ε ≤ ηa,b ( 12 − 2ε)n 2nε − 43 − 2ε ≤ ηa,b (1 − ) ≤ ηa,b . ( 12 − 2ε)n Here, the last inequality follows from the fact that n > 0, 2ε < 12 because ε < 18 < 14 , 6 and 2nε ≥ 2ε + 34 because n ≥ 16ε + 1. Thus, the total flow sent from a to b directly in the second step is at most the excess capacity ηa,b . This concludes the proof. While there is no formula in closed form for the number of vertices needed to guarantee a certain throughput, we can calculate a few entries. The number of vertices needed n to guarantee that our approach improves upon the demand-oblivious bound of 2n−1 is 5 1 5 roughly 700 (with a value of κ = 8 − 8.03 ). The limit of our approach is κ = 8 = 0.625. For n ≥ 2250, we can guarantee a throughput of κ = 0.55, for n ≥ 26000, we can guarantee a throughput of κ = 0.6, and for a guarantees throughput of κ = 0.624, roughly 27 million 13

a

b

a

b

a

b

a

b

Figure 4: The four different vertex-labeled directed 3-regular graphs with two vertices. Note that each vertex has exactly 3 outgoing arcs and out of these c ∈ {0, 1, 2, 3} are self-loops and the other 3 − c are going to the other vertex. vertices are required. However, we mention that our goal was to show a separation, that is, any improvement over the oblivious bound and we conjecture that our approach can be improved to give better bounds for much fewer vertices. We conclude this subsection with an upper bound of 56 for the throughput. Proposition 1. For each κ > 56 , there exists a doubly stochastic 2 × 2 demand matrix Mκ such that (Mκ , κ) is a no-instance of Demand-Aware Throughput.   1−ε ε 5 1 Proof. Let ε = κ − 6 ≤ 6 . We construct Mκ = . There are only four ε 1−ε directed 3-regular graphs with two vertices, which are depicted in Figure 4. The graph in the top left cannot host any demand between the two nodes (and ε > 0). The two graph on the bottom cannot host 56 Mκ since 1 − ε > 32 . Thus, the only possible graph to host κMκ is the graph in the top right. This graph can send κε directly from each node to the other, 1 −κε 2 3 directly via the self loops, and for at least one of the two nodes at most indirectly 3 2 from the node to itself via the other node. Thus, the total demand satisfied from this node to itself is at most 2 1 κε 5 5ε ε2 5 5ε ε2 + − = − − = − +ε−ε− 3 6 2 6 12 2 6 6 2 5 ε 5 < + − ε2 = ( + ε)(1 − ε) = κ(1 − ε). 6 6 6 2

Here, the inequality is due to the fact that ε > ε2 > ε2 for all 0 < ε < 1. This show that the graph in the top right cannot host κ(1 − ε) both from a to a and from b to b. Thus, this graph cannot host κMκ , concluding the proof.

3.2

Direct Throughput

In this section, we show tight lower and upper bounds for the demand-aware direct throughn put. We start with a lower bound of 2n−1 . Afterwards, we show that this bound is tight, 14

that is, for any ε > 0 and any n, there exists a doubly stochastic n × n demand matrix M n such that no directed (2n − 1)-regular graph can host ( 2n−1 + ε)M directly. n , and each doubly stochastic n×n matrix M, Proposition 2. For each n ≥ 1, each κ ≤ 2n−1 it holds that (M, κ) is a yes-instance of Demand-Aware Direct Throughput.

Proof. Let M′ = (2n−1)M = (bi,j )i,j∈[n] . We construct a graph that can host κM directly by describing its adjacency matrix A = (ai,j )i,j∈[n] . We start with the empty graph, that is, A is the n × n matrix with all entries being 0 and increase the values until each row and column of A sums to exactly 2n−1. We say that such a row or column is full and denote the ′ b set of full rows by I and the set of full columns by J . We compute M = (ci,j = ai,j )i,j∈[n] . A i,j If ai,j = 0, then we define ci,j = 0 if bi,j = 0 and ci,j = ∞ if bi,j > 0. Let i, j be the indices among i ∈ / I and j ∈ / J where ci,j is maximum. We then increase ai,j by 1, recompute ci,j , check whether i and/or j should be added to I or J , respectively, and iteratively find the next entry to increase using the same strategy. Since in the end, each row and column is full, the constructed graph is a directed (2n−1)regular graph. We next show that it can host κM directly. To this end, it suffices to show whenever i ∈ I or j ∈ J . Assume towards a contradiction that at that ci,j ≤ 2n−1 n . Since some point there exists an entry ci∗ ,j ∗ with i∗ ∈ I or j ∗ ∈ J where ci∗ ,j ∗ > 2n−1 n the argument will be symmetric, we assume without loss of generality that i∗ ∈ I. Now consider the moment in the algorithm when we increased the value ai∗ ,j ′ for any j ′ for the last time and thereby making row i full. Define the mass mi∗ ,j for each column j as ai∗ ,j − 1 at the considered moment. Let S be the set of all columns j, where mi∗ ,j ≥ 1 b∗ as except for potentially column j ∗ . Note that it holds for all j ∈ S that mii∗,j,j > 2n−1 n otherwise, whenever we increased ai∗ ,j for the last time, we would have increased ai∗ ,j ∗ instead by construction. Equivalently it holds for each j ∈ S that bi∗ ,j > mi∗ ,j 2n−1 . Note n ∗ that P the sum of all masses in row i is at least (2n − 1) − n = n − 1. Hence, it holds , which is equivalent that j∈S mi∗ ,j ≥ n − 1 − mi∗ ,j ∗ . Moreover, recall that ci∗ ,j ∗ > 2n−1 n 2n−1 to bi∗ ,j ∗ > (mi∗ ,j ∗ + 1) n . This implies 2n − 1 =

X j∈[n]

bi∗ ,j ≥

X

bi∗ ,j

j∈S∪{j ∗ }

X =( bi∗ ,j ) + bi∗ ,j ∗ j∈S

X 2n − 1 2n − 1 >( mi∗ ,j ) + (mi∗ ,j ∗ + 1) n n j∈S ≥ (n − 1 − mi∗ ,j ∗ + mi∗ ,j ∗ + 1)

2n − 1 = 2n − 1, n

a contradiction. Thus, each ci,j with i ∈ I or j ∈ J is at most 2n−1 . In the end, all rows 1 bi,j 2n−1 and columns are full. Hence, ai,j = ci,j ≤ n for all i, j ∈ [n]. That is, the graph can n directly host 2n−1 M ≥ κM. This concludes the proof. 15

We next show a matching upper bound. n Proposition 3. For any κ > 2n−1 and any n, there exists a doubly stochastic n × n matrix Mκ such that (M, κ) is a no-instance of Demand-Aware Direct Throughput. n > 0. We assume without loss of generality that n ≥ 2 as clearly Proof. Let ε = κ − 2n−1 1 1 no throughput of 2−1 + ε > 1 is possible. Let δ = min( 2ε , 2n−1 ). Then, we construct the demand matrix   δ δ 1 − δ n−1 . . . n−1 δ   δ  n−1 1 − δ . . . n−1  Mκ =  .. . .. .. δ   . . . δ n−1

δ n−1

n−1

... 1 − δ

Note that each row and column sums to 1. Consider any node v. Since there is positive demand to all other nodes, any solution must contain at least one arc from v to each other node. Thus, at most 2n − 1 − (n − 1) = n arcs are of the form (v, v). We will show that n this is insufficient to host ( 2n−1 + ε)(1 − δ) from v to v directly. Note that n arcs can host n at most 2n−1 flow directly. However, (

n n + (2n − 1)ε − δn − (2n − 1)εδ + ε)(1 − δ) = 2n − 1 2n − 1 n + (2n − 1)ε − εn − ε > 2n − 1 n + ε(2n − 1 − n − 1) = 2n − 1 n + ε(n − 2) = 2n − 1 n ≥ . 2n − 1

The last inequality is due to the fact that n ≥ 2 and ε > 0. This concludes the proof.

4

Weak Throughput Bounds

In this section, we show lower and upper bounds for the worst-case weak (direct) throughput of demand-aware networks. We start with the lower bound. We show the lower bound for Demand-Aware Weak Direct Throughput but notice that the same lower bound also applies to Demand-Aware Weak Throughput by Observation 1. Towards this goal, we first show an intermediate lemma and a simple observation. Intuitively, the lemma shows that we can always round the entries in a matrix with entries between 0 and 1 such that the sums in any row and column remain unchanged and the average entry rounded up is at least as large as the average entry in the whole matrix.

16

P Lemma 1. Let M = (ai,j )i,j∈[n] such that 0 ≤ ai,j ≤ 1 for all i, j ∈ [n], j∈[n] ai,j = si ∈ N P P for all i ∈ [n], and i∈[n] ai,j = tj ∈ N for all j ∈ [n]. Let X = i∈[n] si . Then, there P exists a matrix N = (bi,j )i,j∈[n] such that bi,j ∈ {0, 1} for all i, j ∈ [n], j∈[n] bi,j = si for P P P 2 all i ∈ [n], i∈[n] bi,j = tj for all j ∈ [n], and i∈[n] j∈[n] (ai,j · bi,j ) ≥ Xn2 . Proof. We will build a sequence (C0 , C1 , . . . , Cℓ ) of nP × n matrices where C0 = M, Cℓ = N , h h and Ch = (ci,j )i,j∈[n] for each h ∈ [ℓ] such that j∈[n] ci,j = si for each h ∈ [ℓ] and P P P 2 each i ∈ [n], j∈[n] chi,j = tj for each h ∈ [ℓ] and each j ∈ [n], and i∈[n] j∈[n] ai,j chi,j ≥ Xn2 for each h ∈ [ℓ]. We will ensure that Ch+1 has at least one more integer entry (0 or 1) than Ch . Thus, ℓ ≤ n2 and the procedure always terminates. Note that this will conclude the proof as Cℓ = N then satisfies all requirements of the lemma. We first show that C0 = M satisfies the stated requirement. The sums of entries in row i and column j are by definition si and tj , respectively. Hence, it remains to show P P 2 that i∈[n] j∈[n] a2i,j ≥ Xn2 . To this end, we first flatten the matrix into a vector, that P 2 is, we define zp = ai,j where p = in + j. Note that ni=1 zp = X. Then, we use the Cauchy-Schwarz inequality [28], which states that for any two vectors x = (x1 , x2 , . . . , xq ) and y = (y1 , y2 , . . . , yq ) of non-negative numbers it holds that q X

q q 2  X  X  2 (xi · yi ) ≤ xi yi2 .

i=1

i=1

i=1

Substituting xi = zi and yi = 1 for each i ∈ [n2 ] and q = n2 yields n2 n2 n2 X 2  X  X  2 zi ≤ zi 1 i=1

X2 ≤

⇔

i=1 X X

i=1

 a2i,j n2

i∈[n] j∈[n]

⇔

XX i∈[n] j∈[n]

a2i,j ≥

X2 . n2

Note that this is precisely what we wanted to show. Finally, we show how to construct Ch+1 for a given matrix Ch . To this end, we build a bipartite graph G with a vertex ur for each row r on one side and a vertex vc for each column c on the other side. We add an edge {ur , vc } if and only if chr,c is not an integer. Note that no vertex is incident to exactly one edge as the sum of all entries in a row or column is an integer. Moreover, we assume that the graph contains at least one edge as otherwise we found Cℓ = N already. Then, the graph contains a (simple) cycle as we can start from an arbitrary edge and in each step pick an edge to extend the current path until a vertex is entered for the second time. The subpath between the two occurrences are then a simple cycle by definition. Let (e1 , e2 , . . . , ep ) be the edges in the cycle and note that p is even as the graph is bipartite. Let Eo = {e1 , e3 , . . . , ep−1 } 17

and Ee = {e2 , e4 , . . . , ep } beP the set of the odd-indexed P and even-indexed edges in the cycle, respectively. Let δo = {ur ,vc }∈Eo ar,c and δe = {ur ,vc }∈Ee ai,j . We then make a case distinction whether δo ≤ δe or not. Since both cases are symmetric, we assume without loss of generality that δo ≤ δe . Let ε = min(min{ur ,vc }∈Eo chr,c , min{ur ,vc }∈Ee (1 − chr,c )). Note h that ε > 0. For each edge {ur , vc } ∈ Eo , we set ch+1 r,c = cr,c − ε, for each edge {ur , vc } ∈ Ee , = chr,c . Note that by = chr,c + ε, and for all other pairs (r, c), we set ch+1 we set ch+1 r,c r,c definition of ε, each entry remains in the interval [0, 1] and at least one non-integer entry is replaced by either 0 or 1. Moreover, integer entries in Ch remain unchanged in Ch+1 . It remains to that the sums in P each row remains unchanged between Ch PshowP P and column h+1 and Ch+1 and i∈[n] j∈[n] chi,j ai,j ≤ c a . Towards the first statement, i,j i∈[n] j∈[n] i,j consider an arbitrary is not contained in the cycle, then no entries in row r Prow r. If urP h are changed and so j∈[n] ch+1 = r,j j∈[n] cr,j = sr . If ur is contained in the cycle, then the cycle contains exactly two edges incident to ur and these two edges appear consecutively or are e1 and ep . In either case, exactly one of the edges is contained in Eo and the other is contained in Ee . Hence, exactly one entry is increased by ε and one value is decreased by ε. Thus, the sum within row r remains unchanged and the same argument also holds for each column. Finally, note that  X   X    XX X h+1 h+1 h+1 h+1 (ci,j ai,j ) = (cr,c ar,c ) + (cr,c ar,c ) + (cr,c ar,c ) {r,c}∈Eo

i∈[n] j∈[n]

{r,c}∈Ee

=

 X

=

X X

=

X X

≥

XX

((chr,c − ε)ar,c )



+

{r,c}∈Eo

{r,c}∈E / o ∪Ee

 X

(chr,c + ε)ar,c )



{r,c}∈Ee



(chi,j ai,j ) + ε

 X {r,c}∈Ee

i∈[n] j∈[n]

X

+

(chr,c ar,c )

{r,c}∈E / o ∪Ee



ar,c −

 X

ar,c



{r,c}∈Eo



(chi,j ai,j ) + ε(δe − δo )

i∈[n] j∈[n]

chi,j ai,j .

i∈[n] j∈[n]

This concludes the proof. We next show a simple observation that allows us to view the weak direct throughput from a slightly different angle, that is, we show an equivalent characterization. Observation 4. Given a doubly stochastic matrix M = (ai,j )i,j∈[n] and a value κ, (M, κ) is a yes-instance of Demand-Aware Weak Direct Throughput if and only if there exists an n × n matrix N = (bi,j )i,j∈[n] where each P entry is a non-negative integer and each row and each column sums to 2n − 1 such that i,j∈[n] min((2n − 1)ai,j , bi,j ) ≥ (2n − 1)nκ. Proof. First, assume that (M, κ) is a yes-instance of Demand-Aware Weak Direct Throughput. Then, there exists a matrix M′ = (a′i,j )i,j where a′i,j ≤ ai,j for all i, j ∈ [n] P and a directed (2n−1)-regular graph G such that G can directly host M′ and 18

′ i,j∈[n] ai,j

n

≥ κ.

Let A = (ci,j )i,j∈[n] be the adjacency matrix of G. We show that A fulfills all requirements of matrix N of the observation. First, since A is the adjacency matrix of a directed (2n−1)-regular graph, all its entries are non-negative integers and all rows and columns sum to 2n − 1 each. Second, since G can host M′ directly, it holds that ci,j ≥ (2n − 1)a′i,j and (2n − 1)ai,j ≥ (2n − 1)a′i,j . Thus, X X min((2n − 1)ai,j , ci,j ) ≥ (2n − 1)a′i,j ≥ (2n − 1)nκ. i,j∈[n]

i,j∈[n]

In the other direction, assume a matrix N as described by the observation exists. Then, let G be a graph such that N is the adjacency matrix of G. Note that G is a directed (2n − 1)-regular graph by definition. Moreover, G can host the demand mabi,j ′ ′ trix M′ = (aP i,j )i,j∈[n] = (min(ai,j , 2n−1 P))i,j∈[n] directly. Note that ai,j ≤ ai,j . ′ Finally, i,j∈[n] (2n − 1)ai,j = i,j∈[n] min((2n − 1)ai,j , bi,j ) ≥ (2n − 1)nκ implies P

a′

i,j that i,j∈[n] ≥ (2n−1)nκ = κ. Thus, (M, κ) is a yes-instance of Demand-Aware Weak n (2n−1)n Direct Throughput, concluding the proof.

We next show our lower bound for Demand-Aware Weak Direct Throughput. Theorem 6. Let (M, κ) be an instance of Demand-Aware Weak Direct Through, then (M, κ) is a yes-instance. put where M is an n × n matrix. If κ ≤ 7n−4 8n−4 Proof. Let M = (ai,j )i,j∈[n] . By Observation 4, we need to find a matrix N = (bi,j )i,j∈[n] where each entry bi,j is a non-negative integer and each row and column sum to 2n − 1 such that XX 7n − 4 . min((2n − 1) · ai,j , bi,j ) ≥ (2n − 1)n 8n − 4 i∈[n] j∈[n]

Let a′i,j = (2n − 1)ai,j for all i, j ∈ [n] and M′ = (a′i,j )i,j∈[n] . We will construct N as the sum of two matrices N1 + N2 . First, we set N1 = (⌊(2n − 1) · ai,j ⌋) = (pi,j )i,j∈[n] as the integer part of M′ . Let M′′ = M′ − N1 = (xi,j )i,j∈[n] be the remaining part of M′ . Note that 0 ≤ xi,j < 1 for each i, j ∈ [n]. Moreover, each row and column of M′′ sums to an integer, which is at most n − 1, that is, the sum of all entries in M′′ is at most (n − 1)n = n2 − n. Let X be thisPvalue.PWe can now apply Lemma 1 to construct X2 the matrix N2 = (qi,j )i,j∈[n] such that i∈[n] j∈[n] (xi,j · qi,j ) ≥ n2 and qi,j ∈ {0, 1} for each i, j ∈ [n]. As said before, N = N1 + N2 . Note that each entry in N is an integer by construction and the sum of entries in each row and column is exactly (2n − 1) as the sum in any given row or column is the same in M′′ and in N2 . Since M′ = N1 + M′′ and N = N1 + N2 and each row and column in M′ sums to exactly (2n − 1), the same also holds for N . Hence, it only remains to show that XX 7n − 4 min((2n − 1) · ai,j , bi,j ) ≥ (2n − 1)n . 8n − 4 i∈[n] j∈[n]

19

Note that whenever qi,j = 0, then min((2n − 1) · ai,j , bi,j ) = pi,j = pi,j + qi,j · xi,j and when qi,j = 1, then min((2n − 1) · ai,j , bi,j ) = (2n − 1) · ai,j = pi,j + xi,j = pi,j + qi,j · xi,j . This implies XX

min((2n − 1) · ai,j , bi,j )

i∈[n] j∈[n]

=

XX

(pi,j + qi,j · xi,j )

i∈[n] j∈[n]

= (2n − 1)n − X +

XX

(qi,j · xi,j )

i∈[n] j∈[n]

≥ (2n − 1)n − X +

X2 . n2

Here, the last inequality is due to Lemma 1. We now compute the minimum value for 2 any X ≤ n2 − n. To this end, let f (x) = (2n − 1)n − x + nx2 . We compute the derivative f ′ (x) = n2x2 − 1. Since f is clearly continuous, the minimum is attained at one of the two boundaries (x = 1 or x = n2 − n) or at a place where f ′ (x) = 0. Note that the latter 2 happens (only) at x = n2 . For x = 1, we get f (1) = (2n − 1)n − 1 +

1 7n − 4 > (2n − 1)n − 1 ≥ (2n − 1)n 2 n 8n − 4

for all n ≥ 2. The last inequality follows from the fact that 7n−4 ≥ 56 for all n ≥ 2 8n−4 and (2n−1)n−1 ≥ 65 for all n ≥ 2. Note that for n = 1, the only entry is integer and hence (2n−1)n even κ = 1 yields a yes-instance. For x = n2 − n = (n − 1)n (the upper bound for X), we get ((n − 1)n)2 n2 2 = (2n − 1)n − n + n + (n − 1)2 = (2n − 1)n − n2 + n + n2 − 2n + 1 ≥ (2n − 1)n − 1

f ((n − 1)n) = (2n − 1)n − (n − 1)n +

for all n ≥ 2. Hence, the argument is the same as in the case x = 1.

20

2

Finally, for x = n2 , we get f(

n2 n2 n4 ) = (2n − 1)n − + 2 2 2 4n
n2 = (2n − 1)n 1 − 4(2n − 1)n 4(2n − 1)n − n2
= (2n − 1)n 4(2n − 1)n 2 8n − 4n − n2
= (2n − 1)n 8n2 − 4n 7n2 − 4n
= (2n − 1)n 8n2 − 4n 7n − 4 = (2n − 1)n . 8n − 4

2

Hence, X = n2 yields the minimum of (2n − 1)n 7n−4 . Thus, 8n−4 XX

min((2n − 1) · ai,j , bi,j ) ≥ (2n − 1)n

i∈[n] j∈[n]

7n − 4 , 8n − 4

concluding the proof. To conclude this section, we show upper bounds for Demand-Aware Weak Throughput and Demand-Aware Weak Direct Throughput. Proposition 4. There exists a doubly stochastic 2 × 2 matrix N such that (N , κ) is a no-instance of Demand-Aware Weak Throughput for any κ > 89 . For each positive integer n, there exists a doubly stochastic n × n matrices Mn such that (Mn , κ) is a nowhen n is instance of Demand-Aware Weak Direct Throughput for any κ > 7n−4 8n−4 7n−3 even and for any κ > 8n−4 when n is odd. Proof. We start with theupper  bound for Demand-Aware Weak Throughput. Con5 4 sider the matrix N = 19 · . Note that each row and column sums to exactly 1. There 4 5 are only 4 different directed 3-regular graphs with 2 vertices, which are depicted in Figure 4 and repeated in Figure 5 for convenience. Figure 4. When each arc has capacity 13 , the maximum fraction of N that can be hosted by any graph is 89 which is achieved by both the graph in the top right and bottom  left in Figure 5 as shown next. The graph on the 5 3 top right can host the matrix 19 ≤ N using only direct arcs and the graph in the 3 5  5 4 bottom left can host the matrix 19 ≤ N where 29 flow from a to a is sent over the 4 3 path ((a, b), (b, a)). 21

a

b

a

b

a

b

a

b

Figure 5: Repetition of Figure 4. The four different directed 3-regular graphs with two vertices are shown. We conclude with the upper bound for Demand-Aware Weak Direct Throughput. Consider the matrix   2.5 − a 1.5 2.5 1.5 ...  1.5 2.5 − b 1.5 2.5 . . .  1   2.5 1.5 2.5 − a 1.5 . . . Mn =  ,  2n − 1  1.5 2.5 1.5 2.5 − b . . .   .. .. .. .. .. . . . . . where a = b = 1 whenever n is even and a = 1.5 and b = 0.5 whenever n is odd. We first show that each row and column adds to exactly 1. Whenever n is even, then each 1 ((2.5 + 1.5) n2 − c), where c ∈ {a, b}. That is, each row and column sums row sums to 2n−1 1 to 2n−1 ( 4n − 1) = 1. When n is odd, then each odd row or column sums to 2 n−1 1 1 1 ((2.5 + 1.5) + 2.5 − a) = (2n − 2 + 2.5 − 1.5) = (2n − 1) = 1. 2n − 1 2 2n − 1 2n − 1 Each even row or column sums to 1 n−1 1 1 ((2.5 + 1.5) + 1.5 − b) = (2n − 2 + 1.5 − 0.5) = (2n − 1) = 1. 2n − 1 2 2n − 1 2n − 1 It remains to show that no directed (2n − 1)-regular graph can host a κ-fraction of Mn directly. Assume towards a contradiction that some graph G can host a κ-fraction of Mn directly. We distinguish between even and odd n. We start with the even case and 7n−4 assume κ > 8n−4 . Note that for each row i, at most 3n − 1 arcs of G can be fully 2 1 used and all remaining arcs can host at most 2(2n−1) flow directly. Thus, it holds for the matrix M′n = (a′i,j )i,j∈[n] that is hosted by G and where each entry is at most as large as in Mn that row i sums to at most 2n − 1 − ( 3n − 1) 3n − 2 + 2n − 1 − 3n +1 1 3n 7n − 4 2 2 ( −1+ )= = . 2n − 1 2 2 2(2n − 1) 8n − 4 22

a′

P

n· 7n−4

7n−4 Since there are exactly n rows, it holds that (i,j)∈Vn ×V i,j ≤ 8n−4 = 8n−4 < κ. Thus, G n does not directly host a κ-fraction of Mn , a contradiction. . At most 3 · n−1 +1 We conclude with the case where n is odd and assume κ > 7n−3 8n−4 2 arcs can be used fully and all remaining arcs can only be used with half capacity to host flow directly. This holds true since in odd rows, the number of fully usable arcs is bounded by 3 · n−1 + 2.5 − a = 3 · n−1 + 1 and in even rows, the number is bounded 2 2 n−1 n−1 by 3 · 2 + 1.5 − b = 3 · 2 + 1. Then, it holds for the matrix M′n = (a′i,j )i,j∈[n] that is hosted by G and where each entry is at most as large as in Mn that any row sums to at most

2n − 1 − (3 · n−1 + 1) 1 n−1 2 (3 · +1+ ) 2n − 1 2 2 −1 3n − 3 + 2 + 2n − 1 − 3n−3 2 = ) 2(2n − 1) 6n − 6 + 4 + 4n − 2 − 3n + 3 − 2 = 4(2n − 1) 7n − 3 . = 8n − 4 M′n ,

P

a′

n· 7n−3

7n−3 wee get (i,j)∈Vn ×V i,j ≤ 8n−4 Since there are n rows in = 8n−4 < κ by the same n argument as above. Thus, G does not directly host a κ-fraction of Mn , a final contradiction. This concludes the proof.

We mention in passing that our bounds for the weak direct throughput are tight for n = 1 and all even n, but there is a very small gap for all odd n ≥ 3. We conjecture that the lower bound can be improved in these cases.

5

Computational Complexity

In this section, we analyze the computational complexity of the four problems we study. We first show that Demand-Aware Direct Throughput and Demand-Aware Weak Direct Throughput are polynomial-time solvable. Proposition 5. Demand-Aware Direct Throughput can be solved in O(n3 ) time. Proof. We show that the greedy algorithm that was already used in the proof of Proposition 2 solves Demand-Aware Direct Throughput optimally. We first recall the algorithm. To this end, let M = (ai,j )i,j∈[n] be the input matrix. The algorithm builds the solution graph G by describing its adjacency matrix A = (bi,j )i,j∈[n] . We start with bi,j = 0 ai,j for all i, j ∈ [n]. We then compute bi,j for all i, j ∈ [n] and pick an entry i∗ , j ∗ where this value is maximum and increase bi∗ ,j ∗ by one until the sum in a row or column reaches 2n−1 ai,j at which point all entries in this row or column are ignored. Consider an entry where bi,j is maximum. If bi,j is not increased, then in order to directly host κM, the throughput 23

a

a

i,j i,j is at most κ ≤ bi,j . By the choice of the entry to increase, the throughput is at most bi,j and thus bi,j has to be increased or all further arc additions do not improve the throughput. Since the order in which arcs are added does not matter, it is always optimally to increase bi,j as the algorithm does. ai,j . We can sort all We next analyze the running time. Initially, we compute n2 entries bi,j of them in O(n2 log(n2 )) = O(n2 log(n)) time. We also keep track of the total score in each row and column. We then increase a value bi,j for a total of n(2n − 1) times. Each time, we compute one new entry and insert it into the ordered list of entries, increase the score for one row and one column and if the score reaches 2n − 1, then we remove all entries from that row or column from the sorted list. The time to insert one entry is O(log(n2 )) using binary search and the time to remove all entries for one row or column is O(n2 ). Since we do the former (2n − 1)n times and the latter 2n times in total, the overall running time is in O(n3 ).

We continue with Demand-Aware Weak Direct Throughput. Proposition 6. Demand-Aware Weak Direct Throughput is solvable in O(n4 log(n)) time. Proof. Let (M = (ai,j )i,j∈[n] , κ) be an instance of Demand-Aware Weak Direct Throughput. By Observation 4, (M, κ) is a yes-instance if and only if there exists an n × n matrix N = (bi,j )i,j∈[n] where each entry bi,j is a non-negative integer, each row and each column sums to 2n − 1, and X min((2n − 1)ai,j , bi,j ) ≥ (2n − 1)nκ. i,j∈[n]

Let a′i,j = (2n − 1)ai,j for all i, j ∈ [n]. We show how to find a matrix N as described above in polynomial time using maximum-cost flow. We construct a directed graph with vertex set V = {s, t} ∪ {ri | i ∈ [n]} ∪ {cj | j ∈ [n]}. For each i ∈ [n], we add an arc (s, ri ) with capacity 2n − 1 and cost 0, and for each j ∈ [n], add an arc (cj , t) with capacity 2n − 1 and cost 0. For each i, j ∈ [n], we add three parallel arcs from ri to cj as follows. • An arc with capacity ⌊a′i,j ⌋ and cost 1, • an arc with capacity 1 and cost a′i,j − ⌊a′i,j ⌋, and • an arc with capacity 2n − 1 and cost 0. An example of this construction can be seen in Figure 6. We compute a maximum-cost flow of value n(2n − 1) and check whether the cost is at least (2n − 1)nκ. 24



 0.72 0.04 0.24 3.6 0.2 1.2 c1

0.16 0.12  M = 0.12 0.84 0.72 0.04  0.8 0.6 5M = 0.6 4.2 3.6 0.2 r1 1

s

5

c2 4

r3

4

4

5

t

5

c3

c1

r2

c2

r3

c3

4 5

1

r2

5 5

s

r1

v2

1 5 1 5

v1

t

1 5 4 5 4 5

v3

5

1

Figure 6: The top left shows an input demand matrix M. Below is the matrix (2n − 1)M. The top right shows the constructed instance of maximum-cost flow, where dotted arcs have capacity 2n − 1 = 5 and cost 0, dashed arcs have capacity one and costs depending on their color: green for 0.8, blue for costs 0.6, and red for 0.2. The fully drawn arcs have cost 1 and capacity based on their color: blue for capacity 3 and red for capacity 4. The bottom left shows an optimal solution for the constructed instance corresponding to the solution graph depicted in the bottom left (with the shown capacities  and each time the  0 0.12 0.72 0 . highest cost arc(s) are used). This graph can directly host the matrix 0.12 0.8 0.72 0 0.2 We next show that the construction is correct. To this end, first assume that there exists a matrix N = (bi,j )i,j∈[n] such is a non-negative integer, each row and Pthat each bi,j ′ column in N sums to 2n − 1, and i,j∈[n] min(ai,j , bi,j ) ≥ (2n − 1)nκ. For each i ∈ [n], we send 2n − 1 units of flow over the arcs (s, ri ) and (ci , t). These have cost 0. Moreover for each i, j ∈ [n], we send bi,j units of flow from ri to cj . If bi,j ≤ a′i,j , then these have cost bi,j . If bi,j > a′i,j , then these have total cost a′i,j by construction. By definition of N , there are exactly 2n − 1 units of flow leaving each ri and of flow entering cj . Thus, P 2n − 1 units ′ there is an n(2n − 1)-flow from s to t of cost i,j∈[n] min(ai,j , bi,j ). In the other direction, assume that an n(2n − 1)-flow from s to t of cost x ≥ (2n − 1)nκ exists. Since all capacities and n(2n − 1) are integers, we may assume that the flow over any arc is integral. Now, we build N = (bP i,j )i,j∈[n] where each bi,j is an integer, each row and each column sums to 2n − 1, and i,j∈[n] min((2n − 1)ai,j , bi,j ) = x (and recall that x ≥ (2n − 1)nκ). Let bi,j be the amount of flow send over arcs of the form (ri , cj ). By construction, the total amount of flow leaving any vertex ri and the total amount of flow entering cj is 2n − 1. Hence, each row and each column in N sums to 2n − 1. Finally for a fixed pair (i, j), the cost incurred by sending bi,j units of flow from ri to cj is exactly min(a′i,j , bi,j ) as shown next. The first ⌊a′i,j ⌋ units contribute cost 1 each, the next unit contributes a′i,j − ⌊a′i,j ⌋, and all remaining units contribute cost 0. Thus, the total 25

cost of the flow equals by definition, we have

P

′ i,j∈[n] min(ai,j , bi,j ).

X

Since the cost of the flow is x ≥ (2n − 1)nκ

min(a′i,j , bi,j ) = x ≥ (2n − 1)nκ,

i,j∈[n]

concluding the proof of correctness. Finally, we analyze the running time. The constructed graph has N = 2n + 2 vertices and M ∈ Θ(n2 ) arcs. It can be built in time O(N + M ) = O(n2 ). A maximumcost n(2n − 1)-flow can be computed in O(n(2n − 1)M log(N )) = O(n4 log(n)) time [4], completing the proof. To conclude this section, we next show that Demand-Aware Weak Throughput is NP-hard. Theorem 7. Demand-Aware Weak Throughput is NP-hard. Proof. We present a reduction from the NP-hard problem Exact Cover by 3-Sets [17]. Therein, one is given a universe U = {x1 , x2 , . . . , xN } and a family F = {S1 , S2 , . . . , SM } of subsets of U . Each set Sj ⊆ U has size exactly three and the question is whether there is a subfamily F ′ ⊆ F such that each element xi ∈ U is contained in exactly one set Sj ∈ F ′ . Note that we can assume without loss of generality that N = 3K for an integer K and the size of F ′ is precisely K whenever a solution exists. Thus, we can also assume that M ≥ K. For each element xj , we define αj to be the number of sets Si that contain xj . We construct the demand matrix of a network where the number of vertices is  M N n = 2 + 2N + M + 10(M − K) + 10 + − K + 15M − 10K + 5M. 2 6 S Let V = {s, t} ∪ {ui , vi | i ∈ [M ]} ∪ {yi | i ∈ [N ]} ∪ A ∪ B ∪ Z ∪ i∈[M ] Wi be the set of vertices, where A = {ai | i ∈ [10(M − K)]},  M N B = {bi | i ∈ [10 + − K ]}, 2 6 Z = {zi | i ∈ [15M − 10K]}, and Wi = {wji | j ∈ [5]}. We next state all demands, which are also depicted graphically in Figure 7. To this end, let n∗ = 2n − 1 and we present all demands multiplied by n∗ for notational convenience. The scaled demands du,v from a vertex u to a vertex v are defined as follows and for the sake of readability, we will only define the demands that are larger than 0 and implicitly assume that all demands not mentioned in the following are 0. We start with demand originating from vertex s and set ds,s = n∗ − |A| − K, ds,ui = ds,vi = 12 for all i ∈ [M ], 9 and ds,ai = 10 for all i ∈ [|A|]. The demand originating from t is dt,t = n∗ − |B| − K, 26

1 n∗ − 10

Z

n∗ − 1

n∗ − 1

s

1 2|Z|

Wi 1

9 10

A

αj −1 6|Z|

1 10|Z|

1 10|Z|

1 2

ui

1 n∗ − 11 2 n∗ − |A| − K 1 2

9 10

5 6 1 2 1 2

n∗ − αj

n∗ − 1

yj 11

vi

1 10|Z|

2

n∗ − 4

1 6

9 10

t

B

1 n∗ − |B| − K

K

Figure 7: A graphical representation of the demand matrix constructed in the proof of Theorem 7 (where all demands are multiplied with 2n − 1). The large nodes A, B, Wi , and Z represent sets of vertices and an arc to or from such a set represents one such link to each vertex in the set (and an arc between two such sets represents all pairwise arcs, except for self-loops which are only present from each vertex in the set to itself). For the sake of minimizing visual clutter, only the vertices corresponding to a single element xj (yj ) and a single set Si (ui , vi , and Wi ) are shown. The dashed arcs between yj and vi only exist if xj ∈ Si and there are no demands between vertices corresponding to two different elements or to two different sets. dt,s = K, and dt,bi = 1 for all i ∈ [|B|]. The demand originating from a vertex ui is defined , dui ,vi = 12 , and dui ,wji = 1 for all j ∈ [n]. The demand originating from as dui ,ui = n∗ − 11 2 a vertex vi is dvi ,t = dvi ,ui = 21 , dvi ,vi = n∗ − 4, and dvi ,yj = 65 for all i ∈ [M ] and all j such that xj ∈ Si . We next define the demand originating from each vertex yj and set dyj ,t = 16 , αj −1 dyj ,vi = 56 whenever xj ∈ Si , dyj ,yj = n∗ − αj , and dyj ,zi = 6|Z| for all i ∈ [|Z|]. For each 1 9 i ∗ vertex wj with i ∈ [M ] and j ∈ [5], we set dwji ,wji = n − 1, dwji ,ui = 10 , and dwji ,zℓ = 10|Z| for each ℓ ∈ [|Z|]. It remains to define the demands originating from vertices in A∪B∪Z. For each i ∈ [|A|], 9 we set dai ,ai = n∗ − 1 and dai ,s = 1. For each i ∈ [B], we define dbi ,bi = n∗ − 1, dbi ,t = 10 , 1 1 ∗ and dbi ,zj = 10|Z| for each j ∈ [|Z|]. Finally, for each i ∈ [|Z|], we set dzi ,zi = n − 10 , 1 1 dzi ,aj = 10|Z| for each j ∈ |A|, and dzi ,vj = 2|Z| for each j ∈ [M ]. To conclude the construction, we define a couple of functions and values. For a number x, let ( ( x if x − ⌊x⌋ ≥ 43 ⌈x⌉ if x − ⌊x⌋ ≥ 34 f (x) = and g(x) = ⌊x⌋ otherwise ⌊x⌋ otherwise. 27

N P P P P + 12 H+ 3L 4 Let H = u∈V v∈V f (du,v ) and L = nn∗ − u∈V v∈V g(du,v ). We set κ = . nn∗ This concludes the construction. We next show that the demand originating and terminating in any vertex is 1, that is, the scaled demand is n∗ . Afterwards, we show that there exists a directed n∗ -regular graph d 1 M (where M = ( ni,j∗ )i,j∈[n] ) if and only if there exists an that can host a κ-fraction of 2n−1 exact cover for the original instance. Since the construction can clearly be computed in polynomial time and no demand is negative, this concludes the proof. It is easy to verify that the scaled demand originating from any vertex other than s, yj , or zi for i ∈ [|Z|] and j ∈ [N ] is n∗ . We will skip the formal proof for the sake of conciseness and focus on the slightly non-trivial parts. In a similar manner, all scaled demands terminating in any vertex other than t, vi , and zj for i ∈ [M ] and j ∈ [|Z|] are trivially n∗ and we focus on the listed vertices. The total scaled demand originating in s is

1 9 |A| 1 = n∗ − + M − K = n∗ − (M − K) + M − K = n∗ . (n∗ − |A| − K) + M · + M · + |A| · 2 2 10 10 The total scaled demand originating in a vertex yj is 1 5 αj − 1 1 + 5αj − 6αj + αj − 1 + αj · + (n∗ − αj ) + |Z| · = n∗ + = n∗ . 6 6 6|Z| 6 The total scaled demand originating from a vertex zi is (n∗ −

1 1 1 |A| + 5M 1 10M − 10K + 5M 1 )+|A|· +M · = n∗ − + = n∗ − + = n∗ . 10 10|Z| 2|Z| 10 10|Z| 10 10(15M − 10K)

The total scaled demand terminating in t is (n∗ − |B| − K) + M ·

1 9 1 |B| M N + |B| · + N · = n∗ − −K + + 2 10 6 10 2 6 M N M N − K) − K + + = n∗ . = n∗ − ( + 2 6 2 6

We next analyze the demand terminating in a vertex vi . Note that for each set Si , there are exactly three elements xj such that xj ∈ Si . Hence, the total scaled demand terminating in a vertex vi is 1 1 1 5 1 15 + + (n∗ − 4) + |Z| · + 3 · = n∗ − 4 + 1 + + = n∗ . 2 2 2|Z| 6 2 6

28

Finally, the total scaled demand terminating in a vertex zj is X 1 1 1   X αj − 1  (n − ) + + + |B| · 5· 10 10|Z| 6|Z| 10|Z| ∗

i∈[M ]

j∈[N ]

5M + 10 (3M − N ) + |B| 6

1 + 10 10|Z| + 10( M2 + N6 − K) 5M + 5M − 10N 1 6 = n∗ − + 10 10(15M − 10K) 10N 15M − 6 + 10N − 10K 1 1 1 ∗ 6 + = n∗ − + = n∗ . =n − 10 10(15M − 10K) 10 10 P For the first equality, note that j∈[N ] αj = 3M as each set contains exactly three elements. Thus, the instance we constructed is valid and it remains to prove that it is correct. Before we formally prove the correctness of our construction, we first give a high-level intuition. Given a solution, that n∗ -regular graph and a flow P, we will define P is, a directed di the contribution of an arc e as (Pi ,di )∈P len(P ) ·1e∈Pi and show that a solution has to contain all arcs that can contribute more than 34 and all arcs have to contribute at least 34 . This contains all arcs that can directly host a flow of at least 43 and by construction, there are no pairs (u, v) where the demand from u to v is in the interval ( 21 , 43 ]. Thus, all remaining arcs can directly host a demand of at most 12 and the remaining capacity of 21 has all be used to carry demand over paths of length exactly two. For the demand between ui and vi , there are two possible ways and the vertices s and t will ensure that we can use one of the options exactly K times and the corresponding elements will have to be a cover in the original instance. We now prove the correctness formally and start with the simple direction, that is, we assume that there is an exact cover F ′ for the original instance of Exact Cover by 3-Sets. For each pair (u, v) of vertices, we add g(du,v ) arcs from u to v and whenever g(du,v ) ≥ 1, we add the pair (((u, v)), f (du,v )) to the solution P. That is, we host the integer parts of all demands directly and for all remaining demands, if they are at least 34 , then we also host them directly. We call the arcs P added P so far heavy arcs. Note that the demands hosted directly by heavy arcs is H = u∈V v∈V f (du,v ). We have so far added n∗ outgoing arcs for each vertex in [ {t} ∪ {yi | i ∈ [N ]} ∪ A ∪ B ∪ Z ∪ Wi . = n∗ −

i∈[M ]

Moreover, we have added n∗ −1 outgoing arcs for each vertex in {ui , vi | i ∈ [N ]} and n∗ −K outgoing arcs for s. For each set Si such that Si ∈ F ′ , we add the arcs (s, ui ), (ui , vi ), and (vi , t) to the solution graph and the pairs (((s, ui )), 12 ), (((s, ui ), (ui , vi )), 12 ), (((ui , vi )), 12 ), and (((vi , t)), 12 ) to the solution flow P. For each set Si such that Si ∈ / F ′ , we add the arcs (ui , vi ) and (vi , si ) to the solution graph and the pairs (((ui , vi )), 12 ), (((ui , vi )), 12 ), and (((ui , vi ), (vi , ui )), 12 ) to P. Note that for each vertex yj , we added a heavy arc to vi for 29

each i such that xj ∈ Si and sent a flow of 56 over this arc. Moreover, since F ′ is an exact cover, for each xj , there exists exactly one set Sij ∈ F ′ such that xj ∈ Sij . We finally add the pair (((yj , vij ), (vij , t)), 61 ) to P for each j ∈ [N ]. Note that the heavy arc (yj , vij ) has 16 unused capacity. This concludes the construction of our solution. It remains to show that the constructed graph is a directed n∗ -regular graph and that the constructed flow hosts a κ-fraction of the constructed demand. As shown above, there are exactly n∗ outgoing arcs for each vertex. It is also easy to verify that each vertex has exactly n∗ incoming arcs in the constructed solution. The heavy arcs directly host H of the N 3L + 12 demand (scaled demand (scaled by n∗ ). So it remains to show that the remaining 4 P P by n∗ ) are hosted by our construction, where L = nn∗ − u∈V v∈V g(du,v ). To this end, note that we added exactly L non-heavy arcs. By construction, for each Si ∈ / F ′ , we added 3 two arcs ((ui , vi ) and (vi , ui )) and they together satisfy a demand of 2 . For each set Si ∈ F ′ , we added three arcs ((s, ui ), (ui , vi ), and (vi , t)). The two arcs (s, ui ) and (ui , vi ) satisfy a demand of 32 (scaled by n∗ ) together. The final arc (vi , t) hosts a demand of 21 directly and together with some of the unused capacity of heavy arcs going from yj to vij , they satisfy another demand of 3 16 = 21 . Thus, the total demand (scaled by n∗ ) additionally H+ 3L + N

N 4 12 hosted is 3L + 12 . The total demand hosted is therefore = nκ , that is, we hosted 4 n∗ a κ-fraction of all demands. Thus, the constructed instance of Demand-Aware Weak Throughput is a yes-instance. In the other direction, we assume that the constructed instance of Demand-Aware Weak Throughput is a yes-instance. We first show that that the contribution of all arcs is an equivalent measure for the weak throughput. To this end, let (G, P) be a solution, P di

where (Pi ,dni )∈P ≥ κ. For the sake ofPnotational convenience, we will set d′i = n∗ di and N work with the equivalent assumption (Pi ,di )∈P d′i ≥ κnn∗ = H + 3L + 12 . Let E be the P 4 d′i set of arcs in the constructed solution graph and let cont(e) = (Pi ,di )∈P len(P · 1e∈Pi be ) the contribution of an arc e ∈ E. Note that X e∈E

cont(e) =

X

X

e∈E (Pi ,di )∈P

d′i · 1e∈Pi = len(P )

X (Pi ,di )∈P

d′i = len(Pi ) e∈P X i

X

d′i .

(Pi ,di )∈P

Thus, the contribution of all arcs amount of demand that is Psummed up is exactly the N hosted and we may assume that e∈E cont(e) ≥ H + 3L + . 4 12 Next, note that the contribution of an arc e can only be larger than 34 if it hosts a demand larger than 21 directly. We will show that all such potential arcs have to be part of any solution. This implies that for any pair (u, v) of vertices, any solution contains g(du,v ) arcs from u to v and these host f (du,v ) demand directly, that is, all these arcs (henceforth called heavy arcs) host a demand of H in total. The heavy arcs are exactlyPthe same P heavy arcs as ∗ in the proof of the forward direction and there are 2M +K = nn − u∈V v∈V g(du,v ) = L other arcs in the solution, where exactly one is outgoing from each vertex ui and vi and K are outgoing from s. All these non-heavy arcs can host at most 21 demand directly since there is by construction no pair of vertices where the non-integer part of the demand is in the interval ( 21 , 34 ). This means that they each can contribute at most 43 . So even if all 30

heavy arcs host as much demand as possible directly (which maximizes their contribution per capacity used) and all other arcs contribute 34 each, the total contribution thus far N is only H + 3L = κnn∗ − 12 . This means that some heavy arcs contribute more than 4 what they can host directly. We will now slightly change the accounting and say that the contribution of a heavy arc is the amount what it can host directly and the contribution P d′i · 1e∈Pi where len′ (P ) is the number of non-heavy arcs of all other arcs is (Pi ,di )∈P len′ (P ) in P . Note that no additional demand can be served by just the unused capacity of heavy arcs and hence this re-accounting still precisely describes the weak throughput. We next show that the set of arcs contributing at least 34 did not change and the only arcs that can now contribute strictly more than 43 are arcs of the form (yj , vi ). First, the only heavy arcs that have spare capacity are arcs of the form (s, ai ), (wji , ui ), (yj , vi ), and (bi , t). Since none of the heavy arcs with spare capacity or of the potential S non-heavy arcs are outgoing from vertices in {t} ∪ A ∪ Z or incoming into vertices in i∈[M ] Wi , there are only two possible types of demands that can now contribute more than before the re-accounting: arcs from a vertex in Wi for some i ∈ [M ] to a vertex in Z and arcs from a vertex vj to t. Since no arc from a vertex in Z to a vertex outside Z can contribute 34 , the former is also excluded. This implies that the total additional contribution is a flow of 16 from yj to t for each j ∈ [N ]. These arcs cannot be direct arcs since their contribution could be at 5 < 34 and thus, at most N6 flow is re-accounted. Since each such path contains most 61 + 12 at most 1 heavy arc and at least one non-heavy arc, the re-accouting for this flow adds N to non-heavy arcs. This happens when each such an additional contribution of at most 12 flow uses a path P with len(P ) = 2 and len(P )′ = 1. Thus, any potential solution must consist of all heavy arcs and all other arcs must contribute at least 34 . We now analyze the structure of a potential solution and focus on the non-heavy arc leaving a vertex ui . Note that this arc contributes at least 43 and hence is not (ui , ui ), but (ui , vi ). This implies that ui has exactly one non-heavy incoming arc. Since this arc also contributes at least 34 , it has to also host a demand of at least 12 directly or only together with heavy arcs, that is, it is either (s, ui ) or (vi , ui ). Note that the potential nonheavy outgoing arcs from s are (s, ui ) and (s, vi ) but each vi already has n∗ incoming arcs. Hence, s has exactly K non-heavy outgoing arcs to K vertices ui1 , ui2 , . . . , uiK . We will show that F ′ = {Si1 , Si2 , . . . , SiK } is a solution for the original instance of Exact Cover by 3-Sets. For the corresponding K vertices ui , the two arcs (s, ui ) and (ui , vi ) contribute exactly 34 each by satisfying the demands (s, ui ), (s, vi ) and (ui , vi ). The corresponding vertices vi all have a non-heavy arc (vi , t) which hosts a demand of 12 directly. In order for them to also allow the additional flow of 61 from each vertex yj to t to be hosted, each vertex yj needs to have an outgoing arc to a node vi that has an arc to t. Since there are exactly K such arcs, each vertex vi only has three incoming arcs from vertices yj , and N = 3K, it must hold that no two nodes vi1 and vi2 have incoming arcs from the same vertex vj , that is, the K sets in F ′ do not intersect, that is, F ′ is an exact cover. This concludes the proof. Finally, we conjecture Demand-Aware Throughput to be NP-hard as well, but we are currently not able to prove this. 31

6

Conclusion

We investigated four variants of demand-aware throughput. We showed that two of them (based on direct arcs) can be solved optimally in polynomial time and gave essentially tight lower and upper bounds for them. We also showed the first separation between demand-oblivious and demand-aware throughput in the more general case where demands can be routed via paths of arbitrary length—at least for a sufficiently large number of nodes. This result is based on previous results in the context of randomized and approximation algorithms as well as the probabilistic method; the result is nevertheless completely deterministic. We conclude with some open problems. First, it would be nice to have tight bounds for the two remaining problem variants. While our lower bound for Demand-Aware Throughput is a strong result as it achieves the first separation from the demandoblivious construction, we do not think that it is optimal. Hence, we ask for a different construction that gives better bounds and which also applies for any number n of nodes. We also conjecture that it should be NP-hard to compute the demand-aware throughput, but since we were unable to prove this formally, we leave it as an open problem. It would also be interesting to know what are the matrices that have the lowest demandaware throughput. In the case of demand-oblivious throughput, it is known that these are the permutation matrices. A similar question also arises for the weak throughput. Speaking of weak throughput, we conjecture that the lower bound for Demand-Aware Weak Throughput should be improvable to something like 89 . A matching upper bound for n > 2 is also still open. Finally, to the best of our knowledge, demand-oblivious weak throughput has not been studied before: What is the best bound for demand-oblivious weak throughput?

Acknowledgement This work received financial support from the German Research Foundation (DFG) under research grant SPP 2378: ReNO-2 (project number 511099228) and from the Israel Science Foundation (ISF) grant no. 2497/23.

References [1] Vamsi Addanki, Chen Avin, and Stefan Schmid. Mars: Near-optimal throughput with shallow buffers in reconfigurable datacenter networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):2:1–2:43, 2023. doi: 10.1145/3579312. [2] Vamsi Addanki, Chen Avin, Goran Dario Knabe, Giannis Patronas, Dimitris Syrivelis, Nikos Terzenidis, Paraskevas Bakopoulos, Ilias Marinos, and Stefan Schmid. Ver-

32

milion: A traffic-aware reconfigurable optical interconnect with formal throughput guarantees. CoRR, abs/2504.09892, 2025. doi: 10.48550/ARXIV.2504.09892. [3] Jung Ho Ahn, Nathan L. Binkert, Al Davis, Moray McLaren, and Robert S. Schreiber. Hyperx: Topology, routing, and packaging of efficient large-scale networks. In Proceedings of the 2009 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 1–11. ACM, 2009. doi: 10.1145/1654059.1654101. [4] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network flows – Theory, algorithms and applications. Prentice Hall, 1993. ISBN 978-0-13-617549-0. [5] Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A scalable, commodity data center network architecture. In Proceedings of the ACM SIGCOMM 2008 Conference, pages 63–74. ACM, 2008. doi: 10.1145/1402958.1402967. [6] Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal. Optimal oblivious reconfigurable networks. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1339–1352. ACM, 2022. doi: 10.1145/3519935.3520020. [7] Chen Avin and Stefan Schmid. Revolutionizing datacenter networks via reconfigurable topologies. Communications of the ACM, 68(6):44–53, 2025. doi: 10.1145/3708980. [8] Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network designs of bounded degree. Distributed Computing, 33(3-4):311–325, 2020. doi: 10.1007/S00446019-00351-5. [9] Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network design with minimal congestion and route lengths. IEEE/ACM Transactions on Networking, 30 (4):1838–1848, 2022. doi: 10.1109/TNET.2022.3153586. [10] Navid Hamed Azimi, Zafar Ayyub Qazi, Himanshu Gupta, Vyas Sekar, Samir R. Das, Jon P. Longtin, Himanshu Shah, and Ashish Tanwer. Firefly: A reconfigurable wireless data center fabric using free-space optics. In Proceedings of the ACM SIGCOMM 2014 Conference, pages 319–330. ACM, 2014. doi: 10.1145/2619239.2626328. [11] Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, Tegan Wilson, and Ruogu Zhang. Universal connection schedules for reconfigurable networking. In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4996–5026. SIAM, 2026. doi: 10.1137/1.9781611978971.18. [12] Andrew R. Curtis, Tommy Carpenter, Mustafa Elsheikh, Alejandro López-Ortiz, and Srinivasan Keshav. REWIRE: An optimization-based framework for unstructured data center network design. In Proceedings of the 31st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1116–1124. IEEE, 2012. doi: 10.1109/INFCOM.2012.6195470. 33

[13] Peyman Faizian, Md Atiqul Mollah, Md. Shafayat Rahman, Xin Yuan, Scott Pakin, and Mike Lang. Throughput models of interconnection networks: The good, the bad, and the ugly. In Proceedings of the 25th IEEE Annual Symposium on HighPerformance Interconnects (HOTI), pages 33–40. IEEE Computer Society, 2017. doi: 10.1109/HOTI.2017.21. [14] Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: A hybrid electrical/optical switch architecture for modular data centers. In Proceedings of the ACM SIGCOMM 2010 Conference, pages 339–350. ACM, 2010. doi: 10.1145/1851182.1851223. [15] Nathan Farrington, Alex Forencich, George Porter, P.-C. Sun, Joseph E. Ford, Yeshaiahu Fainman, George C. Papen, and Amin Vahdat. A multiport microsecond optical circuit switch for data center networking. IEEE Photonics Technology Letters, 25(16): 1589–1592, 2013. doi: 10.1109/LPT.2013.2270462. [16] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 53(3):324–360, 2006. doi: 10.1145/1147954.1147956. [17] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7. [18] Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil R. Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel C. Kilper. ProjecToR: Agile reconfigurable data center interconnect. In Proceedings of the ACM SIGCOMM 2016 Conference, pages 216–229. ACM, 2016. doi: 10.1145/2934872.2934911. [19] Albert G. Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, and Sudipta Sengupta. VL2: A scalable and flexible data center network. Communications of the ACM, 54(3):95–104, 2011. doi: 10.1145/1897852.1897877. [20] Chen Griner, Johannes Zerwas, Andreas Blenk, Manya Ghobadi, Stefan Schmid, and Chen Avin. Cerberus: The power of choices in datacenter topology design – A throughput perspective. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(3):38:1–38:33, 2021. doi: 10.1145/3491050. [21] Matthew Nance Hall, Klaus-Tycho Foerster, Stefan Schmid, and Ramakrishnan Durairajan. A survey of reconfigurable optical networks. Optical Switching and Networking, 41:100621, 2021. doi: 10.1016/J.OSN.2021.100621.

34

[22] Nikhil Jain, Abhinav Bhatele, Xiang Ni, Nicholas J. Wright, and Laxmikant V. Kalé. Maximizing throughput on a dragonfly network. In Proceedings of the 2014 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 336–347. IEEE Computer Society, 2014. doi: 10.1109/SC.2014.33. [23] Sangeetha Abdu Jyothi, Ankit Singla, Brighten Godfrey, and Alexandra Kolla. Measuring and understanding throughput of network topologies. In Proceedings of the 2016 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 761–772. IEEE Computer Society, 2016. doi: 10.1109/SC.2016.64. [24] Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, and Duan-Shin Lee. Optimal load-balancing. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1712–1722. IEEE, 2005. doi: 10.1109/INFCOM.2005.1498452. [25] Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, and Minlan Yu. HPCC: High precision congestion control. In Proceedings of the ACM SIGCOMM 2019 Conference, pages 44–58. ACM, 2019. doi: 10.1145/3341302.3342085. [26] William M. Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C. Snoeren, and George Porter. Rotornet: A scalable, low-complexity, optical datacenter network. In Proceedings of the ACM SIGCOMM 2017 Conference, pages 267–280. ACM, 2017. doi: 10.1145/3098822.3098838. [27] Jeffrey C. Mogul and Lucian Popa. What we talk about when we talk about cloud network performance. Computer Communication Review, 42(5):44–48, 2012. doi: 10.1145/2378956.2378964. [28] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. ISBN 0-521-47465-5. [29] Pooria Namyar, Sucha Supittayapornpong, Mingyang Zhang, Minlan Yu, and Ramesh Govindan. A throughput-centric view of the performance of datacenter topologies. In Proceedings of the ACM SIGCOMM 2021 Conference, pages 349–369. ACM, 2021. doi: 10.1145/3452296.3472913. [30] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing, 26 (2):350–368, 1997. doi: 10.1137/S0097539793250767. [31] Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Muhammad Mukarram Bin Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve D. Gribble, Rishi Kapoor, Stephen Kratzer, Nanfang Li, Hong Liu, Karthik Nagaraj, Jason Ornstein, Samir Sawhney, Ryohei Urata, Lorenzo Vicisano, Kevin 35

Yasumura, Shidong Zhang, Junlan Zhou, and Amin Vahdat. Jupiter evolving: Transforming Google’s datacenter network via optical circuit switches and software-defined networking. In Proceedings of the ACM SIGCOMM 2022 Conference, pages 66–85. ACM, 2022. doi: 10.1145/3544216.3544265. [32] Ankit Singla, Philip Brighten Godfrey, and Alexandra Kolla. High throughput data center topology design. In Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 29–41. USENIX Association, 2014. [33] Xin Yuan, Santosh Mahapatra, Michael Lang, and Scott Pakin. LFTI: A new performance metric for assessing interconnect designs for extreme-scale HPC systems. In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 273–282. IEEE Computer Society, 2014. doi: 10.1109/IPDPS.2014.38. [34] Johannes Zerwas, Csaba Györgyi, Andreas Blenk, Stefan Schmid, and Chen Avin. Duo: A high-throughput reconfigurable datacenter network using local routing and control. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):20:1–20:25, 2023. doi: 10.1145/3579449.

36