Edge coloring is the problem of assigning a color to each edge of a multigraph so that no two edges with a common endpoint have the same color. This classic problem, even restricted to bipartite graphs, can be used to model scheduling problems arising in sensor networks [27], switch routing [1], radio-hop networks [56] and optical networks [52], among others. Edge coloring can trace its origins back to the 19th-century works of Tait [55] and Petersen [51], who studied this problem in the context of the four color theorem. Shannon [54] later studied edge coloring in the context of color coding wires in electrical units, and proved that any multigraph G of maximum degree ∆ = ∆(G) admits a ⌊ 3∆ 2 ⌋-edge-coloring; i.e., a coloring using at most ⌊ 3∆ 2 ⌋ colors. (This is tight.) Inspired by this result, Vizing [57] proved that any simple graph can be edge colored using ∆ + 1 colors. Clearly, ∆ colors are necessary to edge color a graph, and for bipartite graphs multiple nearlinear-time ∆-edge-coloring algorithms are known [2,12,29]. For general graphs, several polytime (∆+1)-edge-coloring algorithms are known [25,47,57], and this too is likely optimal, as determining whether a general graph is ∆-edge-colorable is NP-hard [32].
In addition to these optimal polytime algorithms, there exists a simple quasilinear-time (2∆-1)edge-coloring greedy algorithm, which colors each edge with the lowest color unused by its adjacent edges. The greedy algorithm is implementable in many restricted models of computation, and improving upon its coloring guarantees, or even matching them quickly in such models, has been the subject of intense research. Examples include PRAM [41], NC and RNC [6,38,48], dynamic [7,14] and distributed algorithms (e.g., [10,15,19,24,28,50]).
For online algorithms, little progress was made towards beating the greedy algorithm. The only positive results are under random-order edge arrival in "dense" bipartite multigraphs. Specifically, under such stochastic arrivals, Aggarwal et al. [1] showed how to obtain a ∆(1 + o(1)) edge coloring of n-vertex multigraphs if ∆ = ω(n 2 ) and Bahmani et al. [4] showed how to obtain a 1.26∆ edge coloring under the milder assumption that ∆ = ω(log n). The lack of progress for adversarial arrival order is likely explained by the following theorem of Bar-Noy et al. [5].
Theorem 1.1 ( [5], informal). No online edge coloring algorithm can 2∆ -2 edge-color a graph.
However, the lower bound of Bar-Noy et al. requires a number of nodes n exponential in ∆: that is, it only holds for some ∆ = O(log n). Therefore, this lower bound can be thought of as an additive lower bound of ∆ + Ω(log n), rather than a multiplicative lower bound of ≈ 2∆. Put otherwise, it does not preclude a better-than-(2∆ -1) edge-coloring algorithm for ∆ = Ω(log n) large enough. Indeed, Bar-Noy et al. went so far as to conjecture that ∆(1 + o(1))-edge-colorings are computable online for large enough ∆.
). There exists an online algorithm which ∆(1 + o(1)) edge-colors graphs with ∆ = ω(log n).
Our focus. In this paper we study edge coloring under the adversarial online vertex-arrival model of Karp et al. [39], where vertices on one side of a bipartite graph arrive over time, with their edges to previously-arrived neighbors. In this model, an online algorithm colors each edge e upon arrival, immediately and irrevocably. Recall from above that edge coloring in bipartite graphs has multiple applications, including in online settings. Indeed, such an application of edge coloring bipartite graphs to switch routing (with input switches on one side and output switches on the other) was precisely the motivation of Aggarwal et al. [1] to study online edge coloring. The online edge coloring lower bound of [5] holds even for bipartite vertex arrivals. We show that for such arrivals a large enough maximum degree indeed allows to circumvent Bar-Noy et al.'s lower bound, and prove their conjecture. In particular, we present optimal algorithms (up to o(1) terms) both for the known-∆ scenario, as well as for the stricter online problem where ∆(= OP T ) is unknown a priori.
We provide the following optimal results for online edge coloring under adversarial vertex arrivals. For conciseness, we state our results in terms of competitiveness, calling an α • ∆-edge-coloring algorithm α-competitive, as the optimal edge coloring requires at least ∆ colors.
Our first result is an optimal algorithm for known large ∆.
Theorem 1.3. There exists a (1+o(1))-competitive randomized edge coloring algorithm for bipartite graphs of known maximum degree ∆ = ω(log n). A competitive ratio of 1 + o( 1) is optimal -no randomized algorithm is 1 + o(1/ √ ∆) competitive for any ∆.
Like all prior non-trivial online algorithms, the above algorithm assumes a priori knowledge of a critical parameter of the input, namely ∆, which is the optimum number of colors needed to color the bipartite graph. However, in many online scenarios, such assumptions are unreasonable. We show that removing this assumption results in a strictly harder problem, though here too greedy is suboptimal. Our main contribution is an optimal online algorithm for unknown large ∆.
Theorem 1.4. There exists an ( e e-1 + o(1))-competitive randomized edge coloring algorithm for bipartite graphs of unknown maximum degree ∆ = ω(log n). This is optimal (up to o(1) terms)no algorithm is better than e e-1 competitive for unknown ∆.
Remark 1. For simplicity we stated our positive results in theorems 1.3 and 1.4 for ∆ = ω(log n). More generally, our algorithms' competitive ratios are of the form α + O( c log n/∆)) for some constant c ≥ 1 and α = 1 or α = e e-1 , respectively (see Section 4). Thus, we obtain better-than-2 competitive ratios already for sufficiently large ∆ = O(log n). Remark 2. We stated all our positive results for simple graphs, though they hold more generally for any multigraph with maximum edge multiplicity o(∆). (A necessary condition -see Appendix F).
Our upper and lower bounds rely on a new fractional relaxation for edge coloring, of possible independent interest. In particular, we present matching upper and lower bounds for this relaxation, and present a nearly-lossless online rounding of solutions to this relaxation. Using this relaxation, we show a complementary result: a separation between online edge coloring on general and bipartite graphs, which we prove by showing a higher lower bound for the former (as well as a better-thangreedy fractional algorithm for the latter).
Theorem 1.5. No fractional online edge coloring algorithm is better than 1.606(> e e-1 ) competitive for general graphs of unknown maximum degree ∆. On the other hand, there exists a fractional edge coloring algorithm which is 1.777 competitive for general graphs of unknown maximum degree ∆.
To conclude, relying on our new relaxation, we present the first online algorithms beating greedy under any adversarial arrivals. In particular, we prove the conjecture of Bar-Noy et al. and provide tight bounds for the well-studied model of Karp et al., both under known and unknown ∆.
Novel Relaxation. The classic fractional relaxation for edge coloring asks to minimize M x M , subject to M ∋e x e = 1 for every e ∈ E and x M ≥ 0 for every matching M . That is, this relaxation fractionally uses integral matchings to cover each edge. For the online problem, this standard relaxation is not particularly useful, as the set of matchings in the input graph is unknown a priori (since the edge set is unknown). Our first insight is a novel fractional relaxation which allows for more "myopic" assignments upon vertex arrivals -its variables x e,c are the extent to which an edge e is colored c. Specifically, our relaxation integrally uses fractional matchings to cover each edge; i.e., Fractional Algorithms. Our relaxation admits a trivial 1-competitive solution: set x e,c = 1/∆, for each edge and c ∈ [∆]. If ∆ is known a priori, this solution can even be computed by an online fractional algorithm (which must fix the values x ec for each edge e immediately on arrival). By our lower bounds, for unknown ∆, other algorithms are needed. A natural candidate is the greedy "water-filling" algorithm, which continuously increases an arriving edge's assignment for all colors minimizing the maximum load for either endpoint. However, this approach may yield an extremely unbalanced allocation. In particular, it can make a vertex v have load of one in half of the colors used so far and another vertex u have load of one in the other half. Adding an edge (u, v) would then force the algorithm to open a new color -resulting in the trivial 2∆ -1 bound. (See Appendix A.3.) Guided by our lower bounds for fractional algorithms, we derive simple but crucial changes to the water-filling algorithm. First, we use an asymmetric approach, where we pick colors to use based only on the load on the offline vertex. Secondly, in order to bound the load on the online vertex, we cap the value of each edge-color pair. These changes yield bounded loads for the online vertex and a more balanced allocation, resulting in an optimal online fractional edge coloring.
Online Rounding. Given an α-competitive fractional online algorithm, our approach would be to use its α∆ fractional matchings to obtain α∆ integral matchings, or colors, which leave the remaining uncolored subgraph having low maximum-degree (o(∆)). Then using greedy on the remaining uncolored edges requires a further o(∆) colors, or (α+o(1))∆ colors overall. The question is how to compute α∆ colors based on the online fractional edge coloring. One natural way to do so is to repeatedly round these fractional matchings online, using a near-lossless online rounding scheme for fractional matchings ( [11]). Unfortunately, while maximum-degree vertices stand to be matched ≈ ∆ times during such a rounding stage, a constant fraction of these matches would be along previously-matched (colored) edges. To see this, note that each edge has a constant probability of being matched at least twice this way (since each edge has a constant probability of being colored more than once).
We therefore employ a more elaborate approach, repeatedly rounding subsets of multiple fractional edge colorings' fractional matchings. Our guiding intuition is the following simple observation, that the load assigned to the edges of a maximum-degree vertex by an average fractional matching among the α∆ matchings is precisely 1/α. Consequently, rounding a randomly-chosen fractional matching will result in this vertex being matched with probability ≈ 1/α. If most such matches are along previously-unmatched(uncolored) edges, then this vertex's degree in the uncolored graph will decrease at the appropriate rate. However, as exhibited by the previous approach, the probability of matching along an uncolored edge decreases when we use round many fractional matchings. Therefore, we only round a subset of fractional matchings, small enough to not decrease the probability of v being matched along an uncolored edge (due to re-matches), yet large enough to apply tail bound and argue that all high-degree vertices have their uncolored degree decrease at a rate of ≈ 1/α per color used.
How to sample such a number of fractional matchings, not too few and not too many, but just right, for unknown ∆ is not immediate, however, as we do not even know how many fractional matchings we will use (as ∆ is unknown and keeps increasing). To address this, we rely on the fact that ∆ = ω(log n), allowing us to argue that sampling each fractional matching (including matchings which are currently trivial) a priori with appropriate probability p gives the following. We choose p = o(1) (guaranteeing few re-colors) which also satisfies ∆ • p = ω(log n) (in order to have concentration up to (1 ± o(1)) factors on the number of non-trivial colors used), we color a ≈ 1 -p fraction of the edges of high-degree vertices (i.e., ≈ ∆ • p) edges, while using only ≈ α∆ • p colors, all with high probability. We then compute another fractional edge coloring, but this time only on the residual uncolored subgraph. Repeatedly applying this approach (computing another edge colorings, and rounding a sampled subset of its matchings) therefore allows us to decrease the maximum degree of the uncolored graph at the required rate w.h.p. So, after α∆ colors are used this way, we safely run greedy, yielding an (α + o(1))-competitive edge coloring. Plugging in the optimal algorithms for known and unknown ∆ into this rounding scheme then yields our main positive results: optimal randomized online edge coloring algorithms.
Lower Bounds. For our lower bounds (including the tight ones for bipartite graphs) we formulate linear programs capturing constraints satisfied by any α-competitive fractional online algorithms (for our relaxation) when run on a tailor-made family of edge coloring instances. We then present a family of feasible solutions to the dual program, whose value converges to the claimed lower bounds, implying the lower bound on α by LP duality. (See [3] for more examples of this approach.)
Online Edge Coloring. Several previous papers studied edge coloring in online settings [1,4,5,18,20,21,45,46]. Mikkelsen [45,46] studied the online edge coloring problem, but with advice about the future. Favrholdt et al. [18,20,21] studied the "dual" problem of maximizing the number of edges colored using a fixed number of colors. Most relevant to our paper is the work of Motwani et al. [1,4,5]. Aggarwal et al. [1] presented a (1 + o(1))-competitive algorithm for multigraphs with known ∆ = ω(n 2 ). Bahmani et al. [4], inspired by the distributed algorithm of Panconesi and Srinivasan [50], gave a 1.26-competitive algorithm for multigraphs with known ∆ = ω(log n). Both algorithms require random order edge arrivals, and fall short of the guarantees of Conjecture 1.2 ( [5]), either in the competitive ratio or in the requirement of ∆. In contrast, we consider vertex arrivals under the stricter adversarial arrival order, for which we match these conjectured bounds for known ∆, and also achieve optimal bounds for (harder) unknown ∆.
Online Matching. As edge coloring is the problem of partitioning a graph's edges into matchings, it is natural that our work relates to the long line of work on online matching. This problem was introduced in the seminal work of Karp et al. [39], who presented the classic ranking algorithm, which is (1 -1 e ) competitive for bipartite graphs under one-sided arrivals, and proved its optimality. A simpler argument proves this algorithm's optimality even among fractional algorithms (see [22]). Alternative analyses of this algorithm were given over the years ([8, 13, 17, 30]) and another optimal fractional algorithm with further applications, water filling, was given in [36]. Better bounds are known under structural assumptions [9,11,49], and under stochastic arrivals [23,37,43]. See the survey of Mehta [44] for more on this problem and its extensions. Finally, we note the recent interest in online matching in general graphs [26,33,34,58]. Our complementary results of Theorem 1.5 for online edge coloring in general graphs are another step towards a better understanding of matchingtheory-related problems in online models in general graphs.
In this section, we define our new online fractional edge coloring relaxation and discuss several of its properties.
The Classic Fractional Relaxation. The classic relaxation for edge coloring has a nonnegative variable x M for each matching M in G = (V, E), corresponding to the (fractional) extent to which this matching is used in the solution. The objective is to minimize M x M subject to M ∋e x M = 1 for each edge e ∈ E. This relaxation clearly lower bounds the chromatic index; i.e., the minimum number of matchings needed to cover G. A long-standing conjecture of Goldberg and Seymour is that this relaxation is at most one lower than the chromatic index [31,53]. (See [42,Chapter 7.4] for more discussion of this relaxation.) Unfortunately, this relaxation seems somewhat unwieldy in an online setting, as we outline below.
The standard fractional edge coloring relaxation is difficult to use in online settings, where we do not know the edges which will arrive in the future, let alone which matchings G will contain. This motivates us to define a more "myopic" relaxation, which allows us to make our (fractional) assignments immediately upon an edge's arrival (due to one of its endpoints' arrival). Specifically, rather than relax the integrality of the extent to which we use integral matchings, we relax the integrality of the matchings used. That is, while the classic relaxation fractionally uses integral matchings to color edges, our relaxation integrally uses fractional matchings to color edges.
The edge coloring relaxation we consider is thus the following. We say a graph G(V, E) is fractionally k-edge-colorable if there is a feasible solution to the linear program
For any graph G, the minimal number of fractional colors k is equal to G's maximum degree, ∆. We note that in bipartite graphs this relaxation and the classic relaxation are equivalent in an offline sense, in that any solution to one can be transformed to a solution of equal value to the other (for general graphs, there can be a gap of one between the two, as exemplified by the triangle graph).
In an online sense it is not clear how to go from one relaxation to the other, and so we will rely only on our new relaxation.
An LP Formulation. For notational simplicity, rather than discuss fractional algorithms using some k = α • ∆ colors, we will instead use k = ∆ colors and relax the second constraint to
When dealing with fractional solutions, it is easy to "stretch" such a solution to obtain a feasible edge coloring (i.e., satisfying e∋v x e,c ≤ 1) while using ⌈α • ∆⌉ ≤ α • ∆ + 1 colors, and this can be done online. Therefore, our goal will be to minimize α -the competitive ratio.
Online Algorithms for the LP Relaxation. An online fractional edge coloring algorithm must assign x e,c values for all edges e upon arrival, immediately and irrevocably. For example, if ∆ is known a priori, assigning each edge-color pair a value of 1 ∆ trivially yields a 1-competitive online fractional algorithm. If ∆ is unknown, the situation is not so simple, as our lower bounds of Section 5 demonstrate. In the following section we present our online fractional algorithms for unknown ∆, including an optimal algorithm for bipartite graphs.
Our LP relaxation asks to minimize the maximum load of any vertex u in color c, L u (c) e∋u x e,c . The greedy water-filling algorithm, upon arrival of edge e, increases all x e,c for all colors c minimizing the maximum load of either endpoint of e. This natural algorithm is no better than the integral greedy algorithm, however (see Appendix A.1). In our algorithm, upon arrival of a vertex v, we run a variant of the water-filling algorithm on each edge (u, v) in an arbitrary order. One difference in our algorithm compared to the greedy one is that its greedy choice is asymmetric, and is only determined by the current loads of the previously-arrived endpoint, u. The second difference is that we set a bound constraint of β/∆ for each color per edge, where ∆ is the current maximal degree, and β is a parameter of the algorithm which will be determined later. The bound constraints result in bounded load trivially for the online vertex, and by careful analysis, also for the offline vertex. In addition, the bound constraints result in a more balanced allocation, which uses more colors for each edge, but fewer colors overall. A formal description of our algorithm is given in Algorithm 1. Our algorithm is described as a continuous process, but can be discretized easily. for each e = (u, v) ∈ E do for all c ∈ C do 8:
increase x e,c continuously. ⊲ update L u (c), L v (c),U and C .
Our water filling algorithm preserves important monotonicity properties on the loads of any previouslyarrived vertex v. In particular, the order obtained by sorting colors by their loads for v remains invariant following its future neighbors' arrivals. More formally, for each vertex v, we define an order permutation σ v : Z + → Z + , where σ v (i) is the index of v's i th most loaded color index after the vertex v arrives and its edges are fractionally colored (e.g., σ v (1) is the most-loaded color index).
In addition, we define the load of a color in a vertex with respect to this order; i.e., we denote by ℓ t u (i) the load of color σ u (i) for vertex u after its t th neighbor arrives -which we refer to as step t.
In this notation, our monotonicity property will be that ℓ t u (i) ≥ ℓ t u (i + 1) for each u and i, t ∈ Z + . We denote by δ t u the global maximum degree after the arrival of the t th neighbor of vertex u and denote by A u the degree of u when it arrives (e.g., A u = 0 for offline vertices in bipartite graphs). Next, we prove properties of the load of a specific vertex u after its arrival (i.e., for steps t > A u ), at which point the order σ u is already set. For ease of notation we omit the subscript u from variables ℓ, δ and A whenever it will be clear from context (i.e., when considering a single vertex u). In addition, as σ will be clear from context, we will use color k as shorthand notation to σ(k). Moreover, due to space constraints, we defer most proofs to Appendix B.
We first observe that for our bounded water-filling algorithm (as for its unbounded counterpart), the load of u is monotone decreasing with respect to the σ u order, and for each step t, the increase in the load for i ≤ δ t is monotone increasing in the σ u order. Observation 3.1. For all color indices i, and for any t > A
In our analysis, we focus on the critical colors at step T -colors whose load increased at step T and is higher than the following color load. Formally, color k is critical with respect to vertex u and its
Clearly, in order to upper bound the load at step T , it is sufficient to upper bound the load for critical colors k for T . If we let
i=k+1 ℓ T (i) be the total load on colors k + 1, . . . , δ T , we will upper bound the load of color k by
where the first inequality is due to the monotonicity of the loads, and the second inequality is due to the total load being at most δ T . Therefore, we will upper bound the load by proving a lower bound on the index of any critical color, and a lower bound on the total load after this index.
The next lemma plays a key role in both lower bounds. We show that for any color k critical at step T and for all steps A < t ≤ T during which k's load increases, all colors after k that could be increased (i.e. k < i ≤ δ T ) have their load increase by the maximum allowable amount, β/δ t . Lemma 3.2. For a color k critical at step T , for all A < t ≤ T such that ℓ t (k) > ℓ t-1 (k), we have
Using the previous lemma, we bound the minimal index of a critical color at step T .
Next, using Lemma 3.2 and some useful claims in Appendix B we prove a lower bound on V k 2 .
Lemma 3.4. If k is a critical color at step T and k * ≥ max{k, δ A }, we have
Bounding the maximum load. Next, we use the previous lemmas in order to bound the maximum load after an assignment of an edge. Specifically, we will bound the load of ℓ u and ℓ v after coloring the edge (v, u), where v is the newly-arrived vertex. First, it is easy to bound the load of a vertex v for each color after its arrival, since we bound each edge-color pair's value x e,c by
We next use Lemma 3.4 and Equation ( 1) to bound the load of previously-arrived vertex u.
Upper Bounding Algorithm 1's Competitive Ratio We are now ready to bound the competitive ratio of Algorithm 1. First, we show that Algorithm 1 is e e-1 competitive for one-sided bipartite graphs. That is, G(L, R, E) is a bipartite graph and the offline vertices L arrive before the algorithm starts (i.e., A u = 0 for all u ∈ L).
Theorem 3.8. For bipartite graphs under one-sided arrivals, Algorithm 1 is max{β,
, we obtain an ( e e-1 )-competitive algorithm. Proof. We bound the load after coloring of edge (v, u), where v ∈ R is the T th online neighbor of u. First, we bound the load for any color i of v. By Observation 3.5, we have
Finally, in Appendix B we bound our algorithm's competitive ratio on general graphs, proving that it is better than greedy. Theorem 3.9. For any graph, Algorithm 1 is β 2 -β + β logfoot_0 β-1 competitive. Setting β = 1.586, we obtain a 1.777-competitive algorithm.
In this section we show how to round fractional edge-coloring algorithms' output online. Specifically, we will round fractional edge colorings provided by algorithms which assign at most some (small) value ǫ to each edge-color pair, which we refer to as ǫ-bounded algorithms. (As we shall see, the optimal fractional algorithms we will plug into this rounding scheme both satisfy this property.) We now state our main technical result of this section: a nearly-lossless rounding process for bounded algorithms on graphs with high enough lower bound on ∆. Theorem 4.1. For all α ∈ [1, 2] and ǫ ≤ 1, if there exists an ǫ-bounded α-competitive fractional algorithm A for bipartite graphs with unknown maximum degree ∆ ≥ ∆ ′ ≥ 2/ǫ, then there exists a randomized integral algorithm A ′ which is (α + O( 12 (log n)/∆ ′ )-competitive w.h.p on bipartite graphs of unknown maximum degree ∆ ≥ ∆ ′ ≥ c • log n for some constant c.
In the end of the section we show how to use this theorem to obtain a (1 + o(1))-competitive for known ∆. For now, we note that plugging in our optimal fractional algorithm for unknown ∆ into Theorem 4.1, 1 we get an optimal randomized algorithm for edge coloring graphs with unknown ∆. Theorem 4.2. There exists an ( e e-1 +O( 12 (log n)/∆ ′ ))-competitive algorithm for n-vertex bipartite graphs G with unknown maximum degree ∆ ≥ ∆ ′ ≥ c • log n for some absolute constant c.
Remark. The algorithm of Theorem 4.2 requires only a lower bound ∆ ′ ≤ ∆ for some ∆ ′ = ω(log n) in order to output an ( e e-1 + o(1)) • ∆ coloring, and not the exact value of ∆. Alternatively, our algorithm uses ( e e-1 + o(1)) • max{∆, ∆ ′ } colors for any unknown ∆, where the multiplicative approximation ratio is clearly only worse than ( e e-1 + o( 1)) for small ∆ < ∆ ′ -in which case the additive approximation term is only O(∆ ′ ). This result can therefore be read as an asymptotic approximation scheme, trading off between the additive term and the asymptotic competitive ratio.
To describe our rounding scheme, we need the following online rounding scheme of bounded fractional matchings, which motivates our study of bounded fractional edge colorings. Lemma 4.3 (Per-Edge Guarantees [11]). For all ǫ ∈ [0, 1], there exists an online dependent rounding algorithm, marking, which if presented online with a feasible fractional bipartite matching x with an (a priori) guarantee max e x e ≤ ǫ, outputs a matching M which matches each edge e with probability
We now outline our rounding scheme, which consists of phases, as follows. For each phase i, let U i be the uncolored graph at start of phase i. (Initially, U 1 = G.) We compute an α-competitive fractional edge coloring in U i online. Upon the algorithm's initialization, we sample each of the possible α • n fractional matchings of this fractional coloring, i.i.d with probability p. We then round and color the sampled fractional matchings in an online fashion, as follows. Whenever a sampled fractional matching becomes non trivial, we assign it a new color. Whenever a new vertex v arrives, for each phase i in increasing order, we run the next step of marking for each of the sampled fractional matchings of phase i's fractional coloring, and color all newly-matched edges with the color assigned to the relevant fractional matching. Finally, we greedily color the remaining uncolored edges of v. Setting p = o(1) (guaranteeing few re-colors) and also satisfying ∆ • p = ω(log n) (in order to have concentration up to (1±o(1)) factors on number of colors used), this approach will use roughly p • α • ∆(U i ) colors for the i th phase, while decreasing the uncolored subgraph's maximum degree by roughly p • ∆(U i ), or a (1 -p) factor. Thus, using (1/p) log(1/p) phases yield an uncolored subgraph of maximum degree p • ∆ (using α • ∆ colors), which the greedy algorithm colors using 2p • ∆ new colors. This implies Theorem 4.1.
Our online rounding scheme, given an ǫ-bounded fractional edge-coloring algorithm A which is α competitive on graphs of maximum degree at least 2/ǫ, for ǫ = p 4 /(12 log n), works as follows. Let p 12 24(log n)/∆ ′ . We use P ⌈(4/p) log(1/p)⌉ many phases. For phase i, we sample in advance a subset S i of all possible color indices, each taken into S i with probability p. Let U i be the subgraph of edges not colored before phase i. When online vertex v arrives, for each phase i ∈ [P ], we update a fractional coloring x (i) using Algorithm A, based on v's arrival in U i . For all sampled j ∈ S i for which x (i) j (the j th fractional matching of x (i) ) is non trivial, we use a distinct color c i,j to color edges of a matching M i,j computed online by running marking on x (i) j . Finally, all remaining uncolored edges of v are greedily colored using new colors. This is Algorithm 2, below.
We will study changes in the uncolored graph between subsequent phases and the colors used during the phases. For each i, let ∆ i ∆(U i ) be the maximum degree of the online graph not colored by Algorithm 2 Randomized Edge Coloring for Unknown ∆
Parameter p 12 (24 log n)/∆ ′ (≤ 1/10). An ǫ-bounded fractional online edge-coloring algorithm A which is α competitive on graphs U with ∆(U ) ≥ 2/ǫ, for ǫ (p 4 /12 log n). Output: Integral (α + O(p)) • ∆ edge coloring, w.h.p.
1: for all i, set S i ⊆ ⌈α•n⌉ to be such that each j ∈ ⌈α•n⌉ is in S i independently with probability p.
2: for all i, denote by U i the online subgraph of G not colored during phases 1, 2, . . . , i -1.
3: for each arrival of a vertex v ∈ R do 4:
for phase i = 1, 2, . . . , ⌈(4/p) log(1/p)⌉ do 5:
for j ∈ S i with x
if c i,j not set then 8:
set c i,j to be the next unassigned color index.
M i,j ← output of marking run on current
⊲ run next step of marking 10:
if an edge e ∈ M i,j is previously uncolored then ⊲ note: e ∋ v 11:
color e using color c i,j .
12:
run greedy on uncolored edges of v, using colors not assigned during the phases.
phase 1, 2, . . . , i -1. In this section we will show that during each phase i, provided ∆ i is sufficiently large, Algorithm 2 uses some α•∆ i •p(1+O(p)) new colors w.h.p., and obtain an uncolored subgraph To upper bound the number of colors used in phase i, we note that the number of non-trivial (i.e., not identically zero) fractional matchings we round in each iteration is clearly a p-fraction of the (at most ⌈α • ∆ i ⌉) non-trivial colors of x (i) . Therefore, by standard Chernoff bounds (Lemma G.7), if ∆ i is large enough, the number of colors in the phase is small, w.h.p. Lemma 4.4. If ∆ i ≥ (6 log n)/p 3 , then C i , the number of colors used in phase i, satisfies
Lemma 4.4 upper bounds the number of colors used in phase i by α∆ i • p • (1 + p). Our main technical lemma, below, whose full proof is deferred to Appendix C, asserts that these colors result in a decrease of roughly ∆ i • p in the uncolored subgraph's maximum degree during the phase.
Proof Sketch. Let v be a vertex of degree d i (v) ≥ ∆ i /2 in U i . By Lemma 4.3 and the ǫ-boundedness of the fractional algorithm A (and some simple calculations), each edge e ∈ U i is matched in M i,j (j ∈ S i ) with probability x
That is, we match e in M i,j with probability close to its sampled "load" for this color. By Chernoff bounds, as we sample each color of x (i) with probability p, the sampled load on v's edges is d i (v) • p(1 ± O(p)) w.h.p. So, by linearity and another Chernoff bound, the number of times v is matched during the i th phase satisfies
However, M v also counts repeated matchings of edges of v, which do not contribute to v's degree decrease in the uncolored subgraph. We therefore want to bound R v -the number of times a previously-colored edge of v is matched during the phase. By Chernoff's bound and ǫboundedness of the fractional algorithm, the load on each edge in the sampled colors S i , which in expectation is precisely p, is O(p) w.h.p. So, intuitively, we would expect
Of course, as re-matches are not independent of matches, we cannot simply multiply these expressions this way. However, relying on the theory of negative association (see Appendix G.1), the intuitive claim that R v = Θ(d i (v) • p 2 ) w.h.p. can be formalized. We conclude that the degree decrease of vertex v in the uncolored graph during the i th phase is
Taking union bound over all vertices v, the lemma follows.
Theorem 4.1 now follows from Lemma 4.4 and Lemma 4.5. We sketch a proof of this theorem and defer its full proof to Appendix C.
Proof of Theorem 4.1 (Sketch). Clearly, Algorithm 2 colors all edges of G, due to Line 12. By definition, all color classes computed are matchings. As we shall show, the number of colors used during the phases is at most (α + O(p)) • ∆ w.h.p., and the greedy algorithm requires some O(p) • ∆ colors w.h.p., implying our claimed result. We outline this proof using a stronger claim than Lemma 4.5.
Suppose instead of Lemma 4.5 we had that with high probability
Then, by induction we would have ∆ i = ∆ • (1 -p) i and in particular for all i ≤ (1/p) log(1/p) we would have 4 , which in turn would allow us to appeal to union bound to prove that ∆ i = ∆ • (1 -p) i for all i, or in other words ∆ i -∆ i+1 = ∆ i • p, and that the number of colors used in each phase i is at most
Summing over all phases, this would imply that w.h.p., the number of colors used during the phases is
On the other hand, after (1/p) log(1/p) phases we would get a final uncolored subgraph of maximum degree ∆•(1-p) (1/p) log(1/p) ≈ ∆•p w.h.p., and so the greedy step of Line 12 would use at most 2∆•p colors. Overall, Algorithm 2 therefore uses at most (α + O(p)) • ∆ colors for p = O( 5 (log n)/∆ ′ ) and ∆ ≥ 24 log n. Our more involved bounds are due to the slightly looser bounds for ∆ i+1 in terms of ∆ i in Lemma 4.5. See full proof in Appendix C for details.
Applications to Known ∆. Algorithm 2 finds applications for known ∆, too. In particular, by Lemma 4.5 we find that if in each phase i we assign value 1/((1 -p + 7p 2 ) i • ∆) for each edge-color pair, then we obtain a feasible coloring w.h.p., requiring (1 -p + 7p 2 ) i • ∆ colors when the maximum degree is at least (1 -p -4p 2 ) i • ∆, w.h.p.; i.e., this is a (1 + O(p 2 ))-competitive fractional algorithm for uncolored subgraph U i . Replacing algorithm A in Algorithm 2 with this approach then yields, as in the proof of Theorem 4.1, an optimal randomized algorithm for known ∆. Theorem 4.6. There exists a (1 + O( 12 (log n)/∆))-competitive algorithm for n-vertex bipartite graphs G with known maximum degree ∆ ≥ c • log n for some absolute constant c.
In this section we provided optimal online edge coloring algorithms for known and unknown ∆.
In Appendix D we improve the o(1) term in the 1 + o(1) competitive ratio for known ∆. In the following section we present our lower bounds for known and unknown ∆, proving the optimality of our fractional and randomized algorithms, up to o(1) terms.
In this section we present our lower bounds for online edge coloring. We start with by noting that for known ∆, the competitive ratio of (1 + o(1)) we obtain is optimal (up to the exact o(1) term). 2 Observation 5.1. No randomized online edge coloring algorithm is
Proof. By [11], no online matching algorithm outputs a matching of expected size
• n in ∆-regular 2n-vertex bipartite graphs under one-sided arrivals. Given a (1 + ǫ)-competitive edge coloring algorithm, we can randomly pick one of the (1 + ǫ) • ∆ color classes upon initialization and output that as our matching. For ∆-regular graphs on 2n vertices, which have ∆•n edges, this results in a matching of expected size
Our main result of the section is a lower bound for unknown ∆ of e e-1 on the competitive ratio of any fractional online algorithm for our relaxation (and by extension, for any randomized algorithm). To obtain this result, we derive linear constraints that any α-competitive fractional online algorithm must satisfy and formulate these constraints as a family of linear programs. Specifically, we will rely on the modified fractional edge coloring formulation, where the competitive ratio α max v,c e∋v x e,c is the maximum load of any vertex v for color c, and x e,c ≥ 0 for all c ∈ [∆] and x e,c = 0 for all c > ∆, for ∆ the current maximum degree. (See Section 2.1.) We then construct feasible dual solutions to these LPs, which by LP duality imply our claimed lower bounds.
Our first lower bound concerns fractionally edge coloring bipartite graphs.
We can see that each offline vertex has exactly one more neighbor in phase k and the maximum degree in phase k is exactly k. See Figure 1 for an illustrative example. The algorithm will have to be α competitive after each phase, as the adversarial sequence can "terminate early", after essentially presenting disjoint copies of G m ′ for some m ′ ≤ m. 2 A similar argument implies that 1+o(1) competitiveness is impossible on arbitrary multigraphs. See Appendix F.
We use x kj e∈phase k x e,j |{e∈phase k}| to denote the average assignment of color j to edges of phase k. The average load for online vertices of phase k for color j is k • x kj , as each such online vertex has k edges. Consequently, as their average load is at most α, we have the following constraints.
Moreover, since each offline vertex has one more edge during phase k, the average assignment to all edges should cover all edges of phase k, implying the following constraint.
Finally, as the load of all offline vertices (which have only one edge in phase k) for any color j cannot exceed α (and so neither can their average), we have the following constraint.
Combining constraints ( 2)-( 4), yields the following linear program LP m , which lower bounds α.
We construct a series of dual feasible solutions to lower bound α. First, the dual LP is as follows.
Let c(m) ⌊m/e⌋. We know that lim m→∞ c(m
where
We construct a feasible dual solution as follows: We let y 1 = • • • y m = t, and
For any 1 ≤ j ≤ k ≤ m, we have that k • z kj + w j = t = y k . For the first dual constraint, we have
The above is therefore a feasible dual solution, of value
.
When m → ∞, this tends to 1 1-1/e = e e-1 . Consequently, lim m→∞ LP m ≥ e/(e -1), implying our claimed lower bound for fractional online edge coloring of bipartite graphs.
The above construction yields a sparse graph, as the number of vertices in this graph, n = m! + m!(1
is exponential in its maximum degree, m. However, the following change yields a dense graph where the same lower bound still holds. Fix any integer t > 0, in the hard instance, we replace each vertex with t identical copies, and correspondingly, connecting all copies of pairs (u, v) which are adjacent in the sparse graph. The obtained graph is still bipartite and the maximum degree and the number of vertices both increase by a factor of t, to t • m and t • m! log m, respectively. Since we can take t to be arbitrarily large, the graph has maximum degree as high as Ω(n). In order to show that the lower bound still holds, we only need to slightly change the meaning of x kj to be the average assignment of colors (j -1)t + 1, (j -1)t + 2, . . . jt during phase k. Constraints (2)-( 4) still hold with this new meaning in the denser graph. Thus, we conclude that Theorem 5.2 holds for graphs of arbitrarily high degree.
Next, we present a lower bound for general graphs. The lower bound is based on the construction for bipartite graphs, but with more alterations. More specifically, recall that in the construction for bipartite graphs, when the online vertices of phase k arrive, we always connect them to k offline vertices. However, in general graphs, we have more freedom. In phase k, there can be two possible futures: in one we continue the sequence for bipartite graphs; in the other we connect all vertices which arrive during phases k, k + 1, . . . to the vertices which arrived in phase k -1. This example yields a lower bound of 1.606, showing a separation between bipartite and general graphs. 3 We state this lower bound here and defer its proof to Appendix E. Theorem 5.3. No fractional online edge coloring algorithm is better than 1.606 competitive in general graphs.
In this section we present bad examples for a variety of natural edge coloring algorithms for known and unknown ∆.
Here we give a bad example which shows that a family of natural online algorithms, i.e., algorithms that iteratively find a maximal matching, are no better than 2-competitive, even on dense bipartite graphs under one-sided arrivals. Notice that this family of algorithms includes the natural extension of the ranking algorithm. I.e., iteratively find the maximal matching via the optimal, (1 -1/e)competitive, online matching algorithm, ranking -an approach which at first glance one might guess yields an ≈ (e/(e -1))-competitive edge coloring.
The bad example is as follows. The graph is made up of ∆ stars with ∆ -1 leaves each, with the stars' centers, which are offline vertices, connected to a common vertex v, which is the last offline vertex to arrive. It is easy to see that that any algorithm that repeatedly uses a maximal online matching for each color c = 1, 2, . . . would color each star's edges with colors 1, 2, • • • , ∆ -1 following the star's ∆ -1 leaves' arrivals. The ∆ edges of v therefore require a further ∆ colors. Consequently, such an algorithm would use 2∆ -1 colors and is thus 2 competitive. Adding n -∆ 2 -1 isolated dummy nodes with no edges, we get an example with n nodes and maximum degree ∆ = O( √ n). This example therefore rules out this natural family of online edge coloring algorithms for all ∆ = O( √ n).
Our online rounding scheme for fractional edge colorings of Section 4 applies marking to multiple fractional edge colorings. For known ∆, this is done by running marking on some fractional matchings assigning values 1 ∆ ′ , which we refer to as marking ∆ ′ , for increasingly smaller value of ∆ ′ . Here we show an example underlying the need for rounding multiple edge colorings. In particular, we show that simply iteratively coloring the matching output by marking ∆ on the uncolored subgraph -i.e., rounding one trivial edge coloring -results in suboptimally many colors.
To be precise, for c = 1, 2, . . . , ∆, the algorithm considered computes M c , the c-th color class, by running marking ∆ in the subgraph not colored by the first c-1 colors, U c G\ c-1 c ′ =1 M c ′ (and then reverts to some other algorithm on the uncolored graph, say greedy). For simplicity (though this is too good be true), let us assume that marking ∆ matches each edge e with probability precisely 1/∆ in M c if e ∈ U c . Consider a star graph of degree ∆, with the star's center arriving last. Denote by p e,c Pr[e ∈ M c ] the probability that e is colored c. Then, if we run marking ∆ for ∆ phases on the uncolored graph, the probabilities p e,c satisfy the recurrence relation p e,c = 1 ∆ • 1c ′ <c p e,c ′ . But this recurrence captures non-empty bins in a balls and bins process with ∆ balls (colors) thrown into ∆ bins (edges). Specifically, p e,c is the probability of c being the first ball occupying bin e. The expected number of unoccupied bins in the above process, ∆e c p e,c , is ( 1 e + o(1))∆, so this process results in at least ∆ e -o(∆) uncolored edges in the star after ∆ colors used. Consequently, this approach would use at least (1 + 1 e -o(1))∆ colors, even on a star of maximum degree ∆. The above bad example rules out running marking ∆ for the first ∆ colors and then resorting to some other algorithm (say, greedy). More generally, extending this idea to any prefix of colors computed using marking ∆ and then reverting to greedy can be similarly shown to be suboptimal.
For example, standard coupon collector arguments show that the extreme approach of repeatedly running marking ∆ in U c for c = 1, 2, . . . until all edges are colored (i.e., without running greedy) requires at least ∆ log ∆ colors(!), even on a star of maximum degree ∆ whose center arrives last.
In this section, we will give bad examples to rule out a natural candidate algorithm for fractional edge coloring; i.e., water filling. It is easy to see that we can make the level of a color arbitrary large if we only do water filling on one side. On the other hand, the following algorithm is a natural extension of this algorithm which only conducts water filling on the maximum of the two endpoints' loads for any edge (u, v) which arrives. More formally, the algorithm is as follows. for each arrival of a vertex v do 2:
for each e = (u, v) ∈ E do 4:
while c∈[∆] x e,c < 1 do ⊲ initially, x e,c = 0
⊲ "currently active" colors for e
for all c ∈ C do 7:
increase x e,c continuously.
Our first observation here is that water filling is 2 competitive, even under edge arrivals.
Claim A.1. The water filling algorithm is at most 2 competitive under adversarial edge arrivals.
Proof. We only need to prove ℓ ≤ 2 following updates due to the arrival of an edge (u, v). This inequality holds because
where the last inequality holds since we run water filling on the maximum of u and v's loads.
By the above, water filling is always at most 2 competitive. We will show that there exists a hard instance on which water filling is 2 competitive, even under one-sided vertex arrivals in bipartite graphs. We start first with a bad example for vertex arrivals in general graphs, which illustrates the weakness of water filling, and also motivates the hard instance given in Section 5.
A Bad Example for General Graphs. Consider a tree of height n + 1. The root locates in the first level. Each vertex in level k has n -k + 1 children. In the online process, vertices arrive from level n + 1 down to 1. See Figure 2 for an example.
The following claim can be proven by induction and we omit the proof here.
Claim A.2. The loads for all vertices in level k when they first arrive are
When n is large and we set k = 1, then the competitive ratio goes to 2. A Bad Example for Bipartite Graphs. Notice that the bad example above is a bipartite graph, but vertices can arrive from either side. Here we construct a slightly more complicated bipartite example under one-sided arrivals on which water filling is 2 competitive. In the following claim, we use (a, b) to denote (a,
).
Claim A.3. For large enough ∆, there exists a sequence of online vertices such that (2 -4/∆, 4/∆) is achievable for offline vertices.
Proof. We only sketch the sequence here.
(1, 0)
The initial state (1, 0) is achieved by connecting an offline vertex v to ∆/2 online vertices one by one. (a) is reached by having an online vertex u neighbor ∆/2 + 1 offline vertices (1, 0) and one offline vertice (1 + 1/∆, 1/∆), which can be produced in the former step. While (b) is achievable by connecting (2/∆, 1 + 2/∆) (online) and (1, 0) (offline). Finally, we repeat the above process in (a)(b) to get (2 -4/∆, 0). When ∆ is large enough, we conclude that the water filling algorithm is exactly 2 competitive.
Here we provide the missing proofs of lemmas whose proof was deferred from Section 3, restated here for ease of reference. Lemma 3.2. For a color k critical at step T , for all A < t ≤ T such that ℓ t (k) > ℓ t-1 (k), we have
Proof. Suppose there exists A < t ≤ T such that k + 1 ≤ δ t and ℓ t (k + 1) -ℓ t-1 (k + 1) < β/δ t and ℓ t (k)-ℓ t-1 (k) > 0, then we can immediately derive that ℓ t (k) = ℓ t (k+1), since k and k+1 are active at the end of the iteration. But by Observation 3.1 we know that ℓ T (k) = ℓ T (k+1) -a contradiction. Finally, ℓ t (i) -ℓ t-1 (i) ≥ ℓ t (k + 1) -ℓ t-1 (k + 1) for all k < i ≤ δ t by Observation 3.1.
In order to lower bound V 2 k , we first prove the following two useful claims.
Claim B.1. If k is a critical color at step T , then for any j > k and for any S ≥ A ℓ T (j) -ℓ S (j) =
Proof. We prove that for any t ≥ A and δ t ≥ k, then ℓ t (k) > ℓ t-1 (k). Assume not, then we have
Where that last inequality is since k > (1 -1/β)δ T , by Lemma 3.3. Therefore, by Lemma 3.2, we have ℓ t (j) -ℓ t-1 (j) = β/δ t for j ≤ δ t . Consequently,
Next, we bound the total load on the colors after a critical color k.
Proof. By Claim B.1, we have
We now ready to prove the main lower bound volume lemma.
Lemma 3.4. If k is a critical color at step T and k * ≥ max{k, δ A }, we have
where the first inequality is since δ j ≥ j.
In addition, by Lemma 3.3, we have k ≥ δ T • 1 -1 β . Thus, we find that indeed, by Equation ( 1)
Proof. For ease of notation, in this lemma we will let ∆ = δ T . We will consider two cases and show the bound holds for both cases.
As a consequence, by Equation ( 1), we have
where the third inequality above holds because
, by Lemma 3.3 and the last inequality holds because β((1 -β) ∆ δ A + β) + β log ∆ δ A is maximized when ∆ δ A = 1/(β -1) (as can be verified by differentiating with respect to x = ∆ δ A ).
Case 2: k ≤ δ A /β. Note that after the arrival of vertex u, the color load is at most β, by Observation 3.5. We may safely assume that A ≥ βk, since we can always increase A to βk without increasing volume in V k 2 (which we aim to lower bound), by Observation 3.5.
The first inequality holds by Observation 3.5, Claim B.1 and Lemma 3.
The second inequality holds since for j > A, δ j ≥ δ A . For the last inequality, substituting A with βk, a lower bound of A, will only decrease Equation ( 5), since the coefficient of A is non-negative; i.e.
, where the last step follows by Lemma 3.3. Consequently, by Equation (1), we have
Finally, we will need the following simple inequalities for our analysis.
Proof. For both inequalities, we rely on x-1 ≥ log(x) for all x ≥ 1 to obtain the claimed inequalities.
For the first, we have
For the second inequality, we have
Here we give a tight instance for Algorithm 1 in general graphs, showing our analysis in Section 3.1 is tight. We use the same construction shown in Theorem 5.3. Moreover, we assume that the state is "old" until phase k = (β -1)n. We only consider the case when b is sufficiently large. For sufficiently large t, where t < k, we can see the color status for vertex v is roughly
Meanwhile, the color status for vertex u t is roughly
After the arrival of u k , the coin is up, and the final color status for u k (in round n) is
Consequently, our analysis for Algorithm 1 in Section 3.1 is tight and 1.777 is the best achievable competitive ratio for this algorithm.
Here we provide the missing proofs of lemmas and theorem deferred from Section 4, restated here for ease of reference. We start by bounding the number of colors used during each phase.
Lemma 4.4. If ∆ i ≥ (6 log n)/p 3 , then C i , the number of colors used in phase i, satisfies
Proof.
Plugging ǫ = p into the upper multiplicative tail bound of Lemma G.7, we get
The main technical lemma of this section, bounding the maximum degree of the uncolored graph U i+1 in terms of its i th phase counterpart, U i , is as follows.
Lemma 4.5.
Before proving this lemma (in turn deferred to Appendix C.1), we show how it implies our main theorem, restated below. Theorem 4.1. For all α ∈ [1, 2] and ǫ ≤ 1, if there exists an ǫ-bounded α-competitive fractional algorithm A for bipartite graphs with unknown maximum degree ∆ ≥ ∆ ′ ≥ 2/ǫ, then there exists a randomized integral algorithm A ′ which is (α + O( 12 (log n)/∆ ′ )-competitive w.h.p on bipartite graphs of unknown maximum degree ∆ ≥ ∆ ′ ≥ c • log n for some constant c.
Proof. For our proof, we will require the following fact.
For p = 12 (24 log n)/∆ ′ ≤ 1/10 to hold, we need ∆ ′ ≥ 24 • 10 12 • log n. That is, c = 24 • 10 12 . By Lemma 4.5 and Fact C.1,
Consequently, if we let A i [ i ∆ i ≥ (24 log n)/p 4 ] be an indicator for the event that ∆ i is large enough to appeal to Lemma 4.4 and Lemma 4.5 for phase i, then taking union bound (Lemma G.9) over all j < i, we have
Now, by Lemma 4.5 and p ≤ 1/10, we have
On the other hand, by Lemma 4.4, if we denote by C i the number of colors used during the i th phase, then the probability of any of the C i being large is at most
] be the bad event that we use a significantly higher number of colors in phase i than the amount by which we decrease the maximum degree in the uncolored graph in that phase. Then, we have
Therefore, by union bound, we have that with probability at least 1 -10/n, the number of colors used during the phases is at most
Finally, we upper bound the number of colors used by the greedy step of Line 12, by upper bounding the uncolored subgraph's maximum degree before Line 12. We note that by Lemma 4.5 and Fact C.1, we have
Therefore, we find that the final uncolored subgraph U has maximum degree ∆(U ) ≤ ∆ • p, as
Consequently, the greedy step of Line 12 uses a further 2∆ • p colors, and so Algorithm 2 is an (α + 56p)-competitive online edge coloring algorithm.
In this section we will show that each phase i of Algorithm 2 with ∆ i ≥ 24(log n)/p 3 decreases the maximum degree of the uncolored graph by a 1/(1 -p ± O(p 2 )) factor. That is, we will prove Lemma 4.5. As outlined in Section 4, our general approach will be to bound the number of times each near-maximum-degree vertex v in U i is matched during the phase and the number of times it is matched without having an edge colored.
For the remainder of this section, we will need the following random variables. First, for any vertex v and index i, we let d i (v) denote v's degree in the uncolored subgraphs U i . Moreover, for each edge e we let L (i) e,j = x (i) j if j ∈ S i and zero otherwise, and similarly
e,j . We refer to the above as the load of edge e and vertex v in color j of phase i. Finally, we denote by ℓ
e,j and ℓ
v,j the load of the edge e and vertex v in the sampled colors of phase i. Clearly, as each color index j is in S i with probability p, and as each edge is fractionally matched exactly once, we have that E[ℓ
The following lemma asserts that these variables are concentrated around their mean. In all notation, we omit i, which will be clear from context. Lemma C.2. If ∆ i ≥ (24 log n)/p 3 , then 1. for each edge e we have Pr[ℓ e ≥ p(1 + p)] ≤ 1/n 4 , and
Proof. As noted above, E[ℓ e ] = p. Moreover, by the (p 3 /12 log n)-boundedness of f we have that ℓ e = j L e,j is the sum of bounded independent variables L e,j ∈ [0, p 3 /12 log n]. So, by Chernoff bounds (Lemma G.7) with ǫ = p, we obtain
Similarly, as noted above, E[ℓ v ] = p • d i (v). Moreover, as x (i) is a feasible fractional matching, we have |L v,j | ≤ 1 for all j. So, by Chernoff bounds (Lemma G.7), with ǫ = p, we obtain
We will now want to bound the number of times a vertex is matched during a phase. We will rely on Lemma C.2 together with the following lemma.
Lemma C.3. Let x be a fractional matching with max e x e ≤ p 4 /(12 log n). Then for each edge e, marking run with input x outputs a matching M which matches each edge e with probability
Proof. The upper bound on Pr[e ∈ M] is true for all x. For the lower bound, we have that by Lemma 4.3, as p ∈ [0, 1/10] and as we may safely assume n ≥ 2 (otherwise the problem is trivial), we have
Relying on Lemma C.2.2 and Lemma C.3, we obtain the following bounds on M v , the number of times v is matched during the i th phase.
Proof. Let M j v be an indicator variable for the event that v is matched in M i,j . For any instantiation of the variables L e,j , Lemma C.3 implies that each edge e is matched in M i,j with probability L e,j • (1 -3p) ≤ Pr[e ∈ M i,j ] ≤ L e,j , and so by linearity we have
then, by linearity we have both
v is the sum of binary random variables. Moreover, for any subset S i sampled, these {M j v | j ∈ S i } are independent, as all matchings M i,j for j ∈ S i are computed using independent copies of marking. By Chernoff's upper tail bound (Lemma G.7) with ǫ = 2p, we thus obtain
Therefore, we obtain the first claim, as
Similarly, by Chernoff's lower tail bound (Lemma G.7) with ǫ = p, we obtain
From the above we obtain the second claim, as
The above lemma asserts that the number of times a vertex v of high degree in U i is matched during the i th phase is Θ(d i (v)•p). The following lemma relies on the theory of Negative Association (NA, see Appendix G.1) to show that all but O(d i (v) • p 2 ) matches of v during this phase result in an edge of v being colored.
Lemma C.5. If ∆ i ≥ (24 log n)/p 3 , for each vertex v with degree at least
Proof. Fix the realizations of L e,j for all e, j. For any edge e ∋ v, let M e,j
1[e ∈ M i,j ] be an indicator for edge e being matched in iteration j of phase i. By the 0-1 rule, since at most one edge e ∋ v is in any matching, for each j the binary variables {M e,j | e ∋ v} are NA. On the other hand, for j = j ′ the joint distributions {M e,j | e ∋ v} and {M e,j ′ | e ∋ v} are independent. Thus, by closure of NA distributions under independent union (Property (P1)), the {M e,j | j ∈ S i , e ∋ v} are NA. By closure of NA distributions under monotone increasing functions of disjoint variables (Property (P2)), if we let R e j M e,j • min{1, j ′ <j M e,j ′ } denote the number of times e is matched and not colored, then these {R e | e ∋ v} are NA. In this terminology, we have that R v = e∋v R e is the sum of NA variables. Moreover, as the M e,j are NA and as E[M e,j ] ≤ L e,j by Lemma 4.3, we have by the definition of NA variables (see (G.1)) that
Let A = 1[∀e ∋ v : ℓ e ≤ p(1 + p)] be an indicator for the high probability event that every edge e ∋ v has load at most 2p in the sampled matchings.
Therefore, by linearity of expectation,
Observing that for p ≤ 1/10 we have 2 ≤ (1 + p) 2 (1 + √ p), we find that
Now, by Lemma C.2.1 we have for every e ∋ v that Pr[ℓ e ≥ p(1 + p)] ≤ 1/n 3 and so by union bound we have Pr[A] ≤ n • 1/n 3 = 1/n 2 . We therefore conclude that indeed
Lemma 4.5, restated below for ease of reference, follows from lemmas C.4 and C.5 and union bound of relevant subsets of vertices. Lemma 4.5.
Proof. For each vertex v, the decrease in v's degree in the uncolored subgraph during the i th phase, denoted by
, is precisely the number of times v is matched and its matched edge is colored. That is, in the terminology of Lemma C.4 and Lemma C.5,
The first claim then follows by union bound over all maximum degree vertices v in U i .
Now, we let λ p(1 -7p) and note that (1 -λ)
The second claim then follows by union bound over all vertices v of degree
In this section we present an improved algorithm for known ∆. Recall that for the known ∆ regime, using our online rounding scheme of Theorem 4.1 we obtained a 1 + O( 12 (log n)/∆)-competitive algorithm (see Theorem 4.6). In this section we will show how to decrease this competitive ratio to 1 + O( 4 (log n)/∆). That is, we improve the o(1) term when ∆ = ω(log n).
We now turn to describing our approach, starting with an offline description. Iterating over c ∈ [∆], we compute and color a matching M c in the uncolored subgraph G \ c-1 c ′ =1 M c ′ . We then color the remaining uncolored subgraph with new colors using the greedy algorithm. This approach can be implemented online, by iteratively running online matching algorithms on the relevant uncolored subgraphs to compute and color matchings. More concretely, when a vertex v arrives, we iterate over c ∈ [∆] and update M c in the current uncolored graph G \ c-1 c ′ =1 M c ′ , as follows. We run the next step of the online matching algorithm used to compute M c in the current uncolored graph after v's arrival in this subgraph. We then color v's newly-matched edge (if any) using color c. Finally, we run steps of the greedy algorithm on the remaining uncolored edges of v.
For our analysis, we will analyze the above algorithm according to its offline description. Since the greedy algorithm requires a number of colors linear in its input graph's maximum degree, our objective will be to reduce the uncolored subgraph's maximum degree to o(∆) w.h.p. after computing and coloring the first ∆ matchings. In particular, this will require us to match each maximum-degree vertex in G with probability roughly one for each of these ∆ matchings. One way of matching vertices v of degree ∆ in the uncolored subgraph with probability roughly one is to guarantee each edge e ∋ v a probability of roughly 1 ∆ of being matched. An online matching algorithm which does just this is obtained from Lemma 4.3 applied to the trivial fractional matching which assigns a value of 1 ∆ to each edge. We will refer by marking d to the application of marking to the trivially-feasible fractional matching assigning x e = ǫ = 1 d for each edge in a graph of (known) maximum degree at most d.
Corollary D.1. Algorithm marking d is an online matching algorithm which in graphs of maximum degree at most d outputs a matching M which matches each edge e with probability
The first natural approach given Corollary D.1 is to iteratively run marking ∆ . However, as shown in Appendix A.2, this approach is suboptimal. Instead, we will increase the probability of high-degree vertices in the uncolored subgraph to have an edge colored, by running marking d with a tighter upper bound d than ∆ for the uncolored graph's maximum degree for each phase. Unfortunately, upon arrival of some vertex v, we do not know the uncolored graph's maximum degree for all phases, as this depends on future arrivals and random choices of our algorithm. To obtain a tight (up to o(∆)) bound d on the uncolored graph's maximum degree for each phase, we divide the ∆ coloring iterations into phases of ℓ = √ ∆ log n iterations each, during which we use the same upper bound. As ℓ = o(∆) and ℓ = ω(log n), this gives us sharply concentrated upper bounds d i+1 on the resulting uncolored graph's maximum degree at the end of each phase i, which in turn serves as a tight upper bound for the next phase. This results in the desired rate of decrease in the uncolored graph's maximum degree, namely 1 -o(1) per iteration. Greedy thus runs on a subgraph of maximum degree o(∆). Our 1 + o(1) competitive ratio follows.
We now present our online edge coloring algorithm, starting with an offline description. Our algorithm consists of ∆ iterations, equally divided into ∆/ log n phases. During each iteration of phase i, we color a matching output by marking d i run on U i -the uncolored subgraph prior to phase i, for
After all phases, we run greedy with new colors, starting with ∆ + 1. In the online implementation, after each online vertex v's arrival, for phase i = 1, 2, . . . , we run the next step of ℓ = √ ∆ log n independent runs of marking d i in U i , color newly-matched edges and update U i ′ for i ′ > i accordingly. We then greedily color v's remaining uncolored edges with new colors. The algorithm's pesudocode is given in Algorithm 4.
⊲ degree upper bound for each phase
for all i, denote by U i the online subgraph of G not colored by colors [i • ℓ].
for each arrival of a vertex v ∈ R do 5:
for phase i = 0, 1, . . . , ⌊∆/ℓ⌋ -1 do 6:
M c ← output of copy c of marking d i on current U i . ⊲ run next step of marking d i 8:
if an edge e ∈ M c is previously uncolored then ⊲ note: e ∋ v 9:
color e using color c.
run greedy on all uncolored edges of v, using new colors starting from ∆ + 1.
The crux of our analysis is that for each phase i, we have d i ≥ ∆(U i ) w.h.p. Consequently, the final uncolored subgraph after the ∆ iterations (and colors) has maximum degree at most d ⌊∆/ℓ⌋ = o(∆),
Proof. Algorithm 4 computes a feasible edge coloring. It colors each edge, by Line 10, and each color class -computed during iterations or by greedy -constitutes a matching (here we rely on the colors used by greedy and the phases being disjoint). It remains to bound the number of colors this algorithm uses. Each phase requires at most ℓ colors, so the phases require at most ∆ colors. The number of colors the greedy step requires is at most twice the maximum degree of the remaining uncolored subgraph after the phases, which we now bound. Let A i 1[∆(U i ) ≤ d i ] be an indicator for the event that d i upper bounds ∆(U i ). By Lemma D.2 we have that Pr 3 . Also, trivially Pr[A 0 ] = 0. Taking union bound over all i, we find that the probability of any A i not being one is at most
Consequently, all applications of marking d i+1 during phase i + 1 match each edge of U i+1 with probability at least 1 i+1 (1 -11 3 (log d i+1 )/d i+1 ), as required by our analysis for phase i + 1. Moreover, d i ≥ ∆(U i ) for all i ∈ [0, ∆/ℓ] w.h.p. implies that the uncolored subgraph following the ∆/ℓ phases has maximum degree at most
The greedy algorithm therefore colors the remaining uncolored graph using at most a further 18∆ 3/4 log 1/4 n -1 colors. That is, it uses ∆ • O( 4 (log n)/∆) colors in the range ∆ + 1, ∆ + 2, . . . . The theorem follows, including the stated bound for ∆ = ω(log n).
Remark. Algorithm 4 is (1+O( 4 (log n)/∆)) competitive w.h.p. for all ∆ = Ω(log n) large enough, so for ∆ = Ω(log n) large enough it yields a constant competitive ratio strictly smaller than 2.
Here we present our proof for the lower bound for online edge coloring in general graphs.
Theorem 5.3. No fractional online edge coloring algorithm is better than 1.606 competitive in general graphs.
Proof. The adversarial instance has m + 1 possible futures. Neither the number of phases m nor the choice of future are known to the online algorithm. There is a state associated with the input, and there are two possible states, "old" and "new". Initially, the graph contains m! vertices and the state is "old". There are m ′ ≤ m phases in total. We use V k to denote the set of online vertices which arrive in phase k (k ∈ [m ′ ]) and V 0 to denote the initial m! vertices which arrive in phase 0. Moreover, we use v k i to denote the i th vertex arrived in phase k. In phase k, newly-arrived vertices have degree k. If the state is "old", m!/k vertices arrive and the i th vertex, v k i , is adjacent to
On the other hand, if the state is "new" and it changed from "old" to "new" at the end of phase t (k > t), then m!/kt vertices arrive and the i th vertex, v k i , will neighbor
. At the end of phase k, the adversary decide whether to switch state to "new". Notice that the state can only transition from "old" to "new". Again, we let x kj denote the average assignment of color j to edges of phase k, but this time only if the state is "old" during this phase. The following constraints still hold for the same reason as Constraints (2) and (3) for the bipartite hard instance of Theorem 5.2.
m k=j
x i,j ≤ α ∀j.
Furthermore, We use y t k,j to denote the average assignment of color j to edges between V k and V t when the state transitions from "old" to "new" in phase t. (I.e., this is the average assignment of color j to edges of phase k > t, for t the phase at which the transition occurred.)
Again, as each edge between a V t vertex and its neighbor in V k (k > t) must be fractionally colored, we have
Moreover, the maximum load of every vertex for every color is at most α, and so we have
m k=j y t k,j ≤ α ∀1 ≤ t < j ≤ m (10)
To summarize, constraints (6)- (11) for any m are all satisfied by any α-competitive online fractional edge coloring algorithm on this distribution of inputs. Therefore, the optimal value of an LP with objective of minimizing α subject to these constraints is a lower bound on the optimal competitive ratio α of any such online algorithm on general graphs. Using commercial solvers, we solve this LP for m = 50 and find that its optimal value, which lower bounds any algorithm's competitive ratio on general graphs, is 1.606. Again, using the same trick as Section 5.1, we find that this lower bound also holds for dense graphs.
In this section we outline the extension of our positive results to multigraphs (the negative results carry over trivially).
Fractional Algorithms. Our fractional results carry over unchanged to multigraphs. To see this, note that our algorithms' analyses do not require the graph to be simple, as our analysis implies a bound on the maximum load after each edge has its value increased, and the relevant bounds do not require there to be no parallel edges.
Randomized Algorithms. For multigraphs, we "merge" parallel edges into a single edge. When running marking on some fractional matching, we have a merged edge's fractional assignment be the sum of its constituent edges' fractional assignment. If each edge has multiplicity a sufficiently small o(∆) term, this would assign each edge a value of o (1). By the properties of marking (Lemma 4.3), this implies that when we round a fractional matching x to compute a matching M, each edge e is matched in M with probability x e • (1 -o(1)) ≤ Pr[e ∈ M] ≤ x e . Our arguments carry through, though with possibly worse o(1) terms. We note that the above stipulation that each edge have bounded multiplicity is necessary in order to obtain (1 + o(1)) competitiveness for known ∆. 4Observation F.1. No algorithm is (1 + o(1)) competitive on multigraphs of arbitrary multiplicity.
Proof. By [11], no online matching algorithm outputs a matching of expected size c • n in 2-regular 2n-vertex bipartite graphs under one-sided arrivals, for some constant c < 1. Given an input online 2-regular graph, we simulate the online arrival of a multigraph with k copies of each edge of the input (simple) graph, to obtain a 2k-regular multigraph with each edge having multiplicity k. Given a (1 + ǫ)-competitive edge coloring algorithm for multigraphs of maximum degree ∆ = 2k, we can randomly pick one of the (1 + ǫ) • 2k color classes upon initialization and output that matching. For 2-regular graphs on 2n vertices, which have 2 • n edges, this results in a matching in the multigraph (which has 2kn edges) of expected size 2kn (1+ǫ)•2k = n/(1 + ǫ), from which we conclude ǫ = Ω(1).
For completeness, we cite here some useful probabilistic inequalities and notions of negative dependence, starting with the latter.
G.1 Negative Association and Other Negative Dependence Properties.
In our analysis we rely on several notions of negative dependence between random variables. In particular, one notion we will rely on is the notion of negative association, introduced by Khursheed and Lai Saxena [40] and Joag-Dev and Proschan [35].
Definition G.1 (Negative Association [35,40]). A joint distribution X 1 , X 2 , . . . , X n is said to be negatively associated (NA) if for any two functions f, g both monotone increasing or both monotone decreasing, with f ( X) and g( X) depending on disjoint subsets of the X i , f ( X) and g( X) are negatively correlated; i.e.,
Clearly, independent random variables are NA. Another class of NA distributions is captured by the zero-one rule. This rule asserts that if X 1 , X 2 , . . . , X n are zero-one random variables whose sum is always at most one, i X i ≤ 1, then X 1 , X 2 , . . . , X n are NA (see [16]). Additional, more complex, NA distributions can be "built" from simpler NA distributions using the following closure properties.
(P1) Independent Union. If X 1 , X 2 , . . . , X n are NA, Y 1 , Y 2 , . . . , Y m are NA, and {X i } i are independent of {Y j } j , then X 1 , X 2 , . . . , X n , Y 1 , Y 2 , . . . , Y m are NA.
(P2) Concordant monotone functions. Let f 1 , f 2 , . . . , f k : R n → R be functions, all monotone increasing or all monotone decreasing, with the f i ( X) depending on disjoint subsets of the {X i } i . Then, if X 1 , X 2 , . . . , X n are NA, so are f 1 ( X), f 2 ( X), . . . , f k ( X).
Negative association implies several useful properties, including the applicability of Chernoff-Hoeffding type bounds [16] (we elaborate on this below). In addition, NA clearly implies pairwise negative correlation. More generally, NA implies the stronger notion of negative orthant dependence. Definition G.2. A joint distribution X 1 , X 2 , . . . , X n is said to be Negative Upper Orthant Dependent (NUOD), if for all x ∈ R n it holds that
and Negative Lower Orthant Dependent (NLOD) if for all x ∈ R n it holds that
A joint distribution is said to be Negative Orthant Dependent (NOD) if it is both NUOD and NLOD.
Lemma G.3 (NA variables are NOD ( [16,35])). If X 1 , . . . , X n are NA, then they are NOD.
In our analysis we will prove some scaled Bernoulli random variables are NUOD. To motivate our interest in this form of negative dependence, we note that for binary NUOD variables X 1 , X 2 , . . . , X n , we have that for each set I ⊆ [n], Pr[ i∈I X i = 1] ≤ i∈I Pr[X i = 1]. As shown by Panconesi and Srinivasan [50, proof of Theorem 3.2, with λ = 1], this property implies that the moment generating function of the sum of the X i is upper bounded by the moment generating function of the sum of independent copies of the X i variables. A simple extension of their argument shows the same holds if the X i are NUOD scaled Bernoulli variables. As in [50], following the standard proofs of Chernoff-Hoeffding type bounds, this upper bound on the moment generating function implies the applicability of the following upper tail bounds to the sum of NUOD scaled Bernoulli variables "as though these variables were independent". Lemma G.4 (Chernoff Bound for NUOD Bernoulli Variables, [50]). Let X = i X i be the sum of binary NUOD random variables X 1 , X 2 , ..., X n . Then, for any ǫ ∈ [0, 1] and R ≥ E[X]
Lemma G.5 (Bernstein's Inequality for NUOD Scaled Bernoulli Variables). Let X be the sum of NUOD random variables X 1 , X 2 , ..., X n with X i ∈ {0, M i } and M i ≤ M for each i ∈ [n]. Then, if σ 2 = n i=1 V ar(X i ), we have for all a > 0, Pr[X > E[X] + a] ≤ exp -a 2 2(σ 2 + aM/3) .
In addition we will use the following simple coupling argument, stated here for completeness.
Lemma G.6. Let X 1 , X 2 , . . . , X m be random variables and Y 1 , Y 2 , . . . , Y m be binary random variables such that Y i = f i (X 1 , X 2 , . . . , X i ) for all i such that for all x ∈ R m ,
Strictly speaking, our optimal fractional algorithm, Algorithm 1, is not
2/∆ ′ bounded. However, setting our initial lower bound on ∆ to be ∆ ′ in Line 2 yields a 2/∆ ′ -bounded solution without worsening the competitive ratio. (This is equivalent to adding a dummy star which does not increase the maximum degree.)
In Appendix B.1, we show this example is a tight instance for Algorithm 1, which is 1.777 competitive on it.
Aggarwal et al.[1] showed that one cannot even achieve
5/4 -ǫ competitiveness in multigraphs with unbounded edge multiplicities, though under the possibly harder adversarial edge arrival model.