Approximation and Hardness of Token Swapping Given a graph G(V,E) with V1,...,n, we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2o(n) algorithm under the ETH. This is matched with a simple 2O(n*log(n)) algorithm based on a breadthfirst search in an auxiliary graph. We show one general 4approximation and show APXhardness. Thus, there is a small constant delta u003e 1 such that every polynomial time approximation algorithm has approximation factor at least  :119,results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.

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.