This paper initiates the study of a fundamental online problem called online balanced repartitioning. Unlike the classic graph partitioning problem, our input is an arbitrary sequence of communication requests between nodes, with patterns that may change over time. The objective is to dynamically repartition the @math nodes into @math clusters, each of size @math . Every communication request needs to be served either locally (cost 0), if the communicating nodes are collocated in the same cluster, or remotely (cost 1), using inter-cluster communication, if they are located in different clusters. The algorithm can also dynamically update the partitioning by migrating nodes between clusters at cost @math per node migration. Therefore, we are interested in online algorithms which find a good trade-off between the communication cost and the migration cost, maintaining partitions which minimize the number of inter-cluster communications. We consider settings both with and without cluster-size augmentation. For the former, we prove a lower bound which is strictly larger than @math , which highlights an interesting difference to online paging. Somewhat surprisingly, and unlike online paging, we prove that any deterministic online algorithm has a non-constant competitive ratio of at least @math , even with augmentation. Our main technical contribution is an @math -competitive algorithm for the setting with (constant) augmentation. We believe that our model finds interesting applications, e.g., in the context of datacenters, where virtual machines need to be dynamically embedded on a set of (multi-core) servers, and where machines migrations are possible, but costly.
BRP also has connections to online packing problems, where items of different sizes arriving over time need to be packed into a minimal number of bins @cite_16 @cite_9 . In contrast to these problems, however, in our case the objective is not to minimize the number of bins but rather the number of links'' between bins, given a fixed number of bins.
@cite_9 @cite_16
2078659331 2016393589
A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in Richey [1991] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus, Harmonic++ provides the best upper bound for the online bin packing problem to date. Abstract In this paper, we study the 1-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. We present a new linear-time algorithm, the Modified Harmonic Algorithm and show, by a novel use of weighting functions, that it has an asymptotic worst-case performance ratio less than 3 2 + 1 9 + 1 222 = 1.(615) ∗ . We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least 3 2 + 1 9 = 1.61 ∗ . Then we show how to successively construct classes of improved linear-time on-line algorithms. For any algorithm in any of these classes, the performance ratio is at least 3 2 + 1 12 = 1.583 ∗ . We present an improved algorithm called Modified Harmonic-2 with performance ratio 1.612 … and present an approach to construct linear-time on-line algorithms with better performance ratios. The analysis of Modified Harmonic-2 is omitted because it is very similar to that of Modified Harmonic, but it is substantially more complicated. Our results extend to orthogonal packings in two dimensions.