Placement Delivery Arrays from Combinations of Strong Edge Colorings It has recently been pointed out in both of the works C. Shanguan, Y. Zhang, and G. Ge, IEEE Trans. Inform. Theory, 64(8):5755xe2x80x935766 (2018) and Q. Yan, X. Tang, Q. Chen, and M. Cheng, IEEE Commun. Lett., 22(2):236xe2x80x93239 (2018) that placement delivery arrays (PDAs), as coined in Q. Yan, M. Cheng, X. Tang, and Q. Chen, IEEE Trans. Inform. Theory, 63(9):5821xe2x80x935833 (2017), are equivalent to strong edge colorings of bipartite graphs. In this paper we consider various methods of combining two or more edge colorings of bipartite graphs to obtain new ones, and therefore new PDAxe2x80x99s. We find that combining PDAs in certain ways also gives a framework for obtaining PDAxe2x80x99s with more robust and flexible parameters. We investigate how the parameters of certain strong edge colorings change after being combined with another, and we compare the parameters of the resulting PDAxe2x80x99s with those of known ones.

Distributed balanced color assignment on arbitrary networks Abstract   Consider a scenario in which a set of n agents hold items, where each item can be of one out of m possible types (colors). The agents are connected by an arbitrary network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible: in the particular case where m is a multiple of n, each agent must have exactly    m    n    colors. More formally, the goal is to let the agents agree on an assignment of colors to agents such that the following two conditions hold:  (i)   each color is assigned to exactly one agent;   (ii)   each agent has at least    xe2x8cx8a  m    n  xe2x8cx8b    and at most    xe2x8cx88  m    n  xe2x8cx89    colors.    Among all possible such repartitions, we seek for the one that minimizes the number of xe2x80x9cchangesxe2x80x9d (measured in terms of misplaced items) with respect to the initial configuration. In other words, our aim is to design a distributed algorithm that finds a balanced coloring of minimum cost, where the cost of a coloring is the number of items that need to be relocated.  This kind of questions, usually modeled as generalized bipartite matching problems, have been studied in the distributed setting only on clusters of commodity nodes with the aim of copying with realworld massive instances, which may involve millions of agents and colors. Here we propose the first distributed algorithm designed to run on an arbitrary network with the agents as nodes. Our algorithm turns out to be efficient in terms of both time and message complexity for a large class of graphs. Our results can be outlined as follows.  We prove a lower bound    xcexa9  (  m    n  xe2x8bx85    D    2    )    on message complexity, where D is the diameter of the graph, that holds for any approximation algorithm whose solution has cost at most    2  (  xcexb1  xe2x88x92  2  )    xcexb1    times the cost of any optimal solution, for every constant    xcexb1  u003e  2   . We give a distributed deterministic algorithm with time complexity    O  (  max  xe2x81xa1      n    2    ,  D  log  xe2x81xa1  q    )    and message complexity    O  (    n    log  xe2x81xa1  n    xe2x8bx85  (  log  xe2x81xa1  q    m  log  xe2x81xa1  m  )  )   , where q is the maximum number of items of a given color held by any agent. We show that the cost of our solution for arbitrary graphs is at most    (  2    xcexb4  )    times the optimal cost, for any    xcexb4  u003e  0   . We finally observe that, for large diameter graphs (i.e.,    D    xcexa9  (    n    xcfxb5    )   ,    xcfxb5  u003e  0   ), we get matching lower and upper bounds on message complexity for the vast majority of instances of potential interest, that is, instances with polynomial number of colors and (up to) superexponential number of items.