In this manuscript, we consider the problems of channel assignment in wireless networks and data migration in heterogeneous storage systems. We show that a soft edge coloring approach to both problems gives rigorous approximation guarantees. In the channel assignment problem arising in wireless networks a pair of edges incident to a vertex are said to be conflicting if the channels assigned to them are the same. Our goal is to assign channels (color edges) so that the number of conflicts is minimized. The problem is NP-hard by a reduction from Edge coloring and we present two combinatorial algorithms for this case. The first algorithm is based on a distributed greedy method and gives a solution with at most @math more conflicts than the optimal solution.The approximation ratio if the second algorithm is @math , which gives a ( @math )-factor for dense graphs and is the best possible unless P = NP. We also consider the data migration problem in heterogeneous storage systems. In such systems, data layouts may need to be reconfigured over time for load balancing or in the event of system failure upgrades. It is critical to migrate data to their target locations as quickly as possible to obtain the best performance of the system. Most of the previous results on data migration assume that each storage node can perform only one data transfer at a time. However, storage devices tend to have heterogeneous capabilities as devices may be added over time due to storage demand increase. We develop algorithms to minimize the data migration time. We show that it is possible to find an optimal migration schedule when all @math 's are even. Furthermore, though the problem is NP-hard in general, we give an efficient soft edge coloring algorithm that offers a rigorous @math -approximation guarantee.
Fitzpatrick and Meertens @cite_13 have considered a variant of graph coloring problem (called the Soft graph coloring problem) where the objective is to develop a distributed algorithm for coloring vertices so that the number of conflicts is minimized. The algorithm repeatedly recolors vertices to quickly reduce the conflicts to an acceptable level. They have studied experimental performance for regular graphs but no theoretical analysis has been provided. Damaschke @cite_6 presented a distributed soft coloring algorithm for special cases such as paths and grids, and provided the analysis on the number of conflicts as a function of time @math . In particular, the conflict density on the path is given as @math when two colors are used, where the conflict density is the number of conflicts divided by @math .
@cite_13 @cite_6
1485830228 2129185967
This paper reports on a simple, decentralized, anytime, stochastic, soft graph-colouring algorithm. The algorithm is designed to quickly reduce the number of colour conflicts in large, sparse graphs in a scalable, robust, low-cost manner. The algorithm is experimentally evaluated in a framework motivated by its application to resource coordination in large, distributed networks. In a soft coloring of a graph, a few adjacent vertices may receive the same color. We study soft coloring in the distributed model where vertices are processing units and edges are communication links. We aim at reducing coloring conflicts as quickly as possible over time by recoloring. We propose a randomized algorithm for 2-coloring the path with optimal decrease rate. Conflicts can be reduced exponentially faster if extra colors are allowed. We generalize the results to a broader class of locally checkable labeling problems on enhanced paths. A single result for grid coloring is also presented.