More Like this

1. Balanced shifted tableaux

   https://doi.org/10.1016/j.disc.2023.113836  

   Gao, Jiyang; Gao, Shiliang; Gao, Yibo (March 2024, Discrete Mathematics)
2. Locally Balanced Constraints

   https://doi.org/10.1109/ISIT44484.2020.9173933  

   Gabrys, Ryan; Kiah, Han Mao; Vardy, Alexander; Yaakobi, Eitan; Zhang, Yiwei (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)
3. Load balanced distributed directories

   https://doi.org/10.1016/j.ic.2021.104700  

   Rai, Shishir; Sharma, Gokarna; Busch, Costas; Herlihy, Maurice (January 2021, Information and Computation)
4. Joinable Parallel Balanced Binary Trees

   https://doi.org/10.1145/3512769  

   Blelloch, Guy; Ferizovic, Daniel; Sun, Yihan (June 2022, ACM Transactions on Parallel Computing)

   In this article, we show how a single function,join, can be used to implement parallelbalanced binary search trees(BSTs) simply and efficiently. Based onjoin, our approach applies to multiple balanced tree data structures, and a variety of functions for ordered sets and maps. We describe our technique as an algorithmic framework calledjoin-based algorithms. We show that thejoinfunction fully captures what is needed for rebalancing trees for a variety of tree algorithms, as long as the balancing scheme satisfies certain properties, which we refer to asjoinabletrees. We discuss four balancing schemes that are joinable: AVL trees, red-black trees, weight-balanced trees, and treaps. We present a variety of tree algorithms that apply to joinable trees, includinginsert,delete,union,intersection,difference,split,range,filter, and so on, most of them also parallel. These algorithms are generic across balancing schemes. Many algorithms are optimal in the comparison model, and we provide a general proof to show the efficiency in work for joinable trees. The algorithms are highly parallel, all with polylogarithmic span (parallel dependence). Specifically, the set-set operationsunion,intersection, anddifferencehave work\( O(m\log (\frac{n}{m}+1)) \)and polylogarithmic span for input set sizes\( n \)and\( m\le n \). We implemented and tested our algorithms on the four balancing schemes. In general, all four schemes have quite similar performance, but the weight-balanced tree slightly outperforms the others. They have the same speedup characteristics, getting around 73\( \times \)speedup on 72 cores (144 hyperthreads). Experimental results also show that our implementation outperforms existing parallel implementations, and our sequential version achieves close or much better performance than the sequential merging algorithm in C++ Standard Template Library (STL) on various input sizes. 

   more » « less
5. Doubly Balanced Connected Graph Partitioning

   https://doi.org/10.1145/3381419  

   Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil (April 2020, ACM Transactions on Algorithms)

   null (Ed.)

   We introduce and study the doubly balanced connected graph partitioning problem: Let G =( V , E ) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p ( V )=∑ j &isin V p ( j ) = 0. The objective is to partition G into ( V 1 , V 2 ) such that G [ V 1 ] and G [ V 2 ] are connected, ∣ p ( V 1 )∣,∣ p ( V 2 )∣≤ c p , and max{ ∣ V 1 / V 2 ∣,∣ V 2 / V 1 ∣} ≤ c s , for some constants c p and c s . When G is 2-connected, we show that a solution with c p =1 and c s =2 always exists and can be found in randomized polynomial time. Moreover, when G is 3-connected, we show that there is always a “perfect” solution (a partition with p ( V 1 )= p ( V 2 )=0 and ∣ V 1 ∣=∣ V 2 ∣, if ∣ V ∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p ( V )≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types. 

   more » « less