Papers for
parallel computing teams
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Load balancing split tasks optimize fragment counts for many bins
Load Balancing with Item Fragmentation and More Bins than Items: Linear-Time and Exact
Abstract: We study a fundamental load-balancing problem in which $N$ items of strictly positive integer sizes with total size $W$ must be assigned to $B$ bins, with items allowed to be divided into integer-size fragments across bins. Each bin must receive a load of either $\lfloor W/B \rfloor$ or $\lceil W/B \rceil$, ensuring that the loads of any two bins differ by at most one unit. Under this constraint, the objective is to minimize the maximum number of distinct item fragments placed into any single bin. This problem is NP-hard and there exists an $(\mathrm{OPT}+1)$-approximation algorithm that runs in $O(N \log N + B)$ time [Kobert et al., 2014]. The existing algorithm is employed by several widely used production codes for phylogenetic reconstruction. Here, we focus on the case $B \ge N$, that is, bins are at least as numerous as items. This setting arises pervasively in modern parallel and distributed systems, as well as in iterative algorithms that rebalance their workload at every step. In this context, bins are machines or machine cores, and items represent computational tasks (jobs). Our central contribution is a remarkably simple $O(N)$-time algorithm that computes an optimal assignment in this setting; this assignment is encoded using $O(N)$ space. In particular, we prove that an optimum always exists in which every bin receives at most two fragments and provide a characterization of when one fragment per bin suffices. Our result strictly improves the $(\mathrm{OPT}+1)$-approximation of Kobert et al. in the many-bins setting and, together with it, yields a strongly polynomial-time $(\mathrm{OPT}+1)$-approximation algorithm for the general setting, as it removes the dependency on the number $B$ of bins.
Minimum bisection split found faster with improved counting method
Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection
Abstract: The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them. We give a single exponential time algorithm for minimum bisection, running in time $2^{O(k)}n^{O(1)}$. This improves the previous bound of $2^{O(k\log k)}n^{O(1)}$ due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time $2^{O(k)}n^{O(1)}$ a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.
Most 3 uniform hypergraphs require only minimal edge colors
Almost All 3-uniform Hypergraphs are Class 1
Abstract: The chromatic index $χ'(H)$ of a hypergraph $H$ is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree $Δ(H)$, and when $χ'(H)= Δ(H)$, we say that $H$ is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for $n^{-2/3-1/200}\leq p \leq 0.99$ that the $3$-uniform binomial random hypergraph $H\sim H_{n,p}^{(3)}$ is Class 1 with high probability. We also show that this result doesn't hold for uniformities above $3$. For a broad range of $p$, when $k \geq 4$ and $k \nmid n$, the hypergraph $H \sim H_{n,p}^{(k)}$ is with high probability not Class 1.
Communication efficient edge coloring with near optimal colors and local lemma use
Communication-Efficient $(1+\varepsilon)Δ$-Edge Coloring and Lovász Local Lemma
Abstract: We study edge coloring in the two-party edge-partition model, where Alice and Bob each know part of the edge set and must jointly produce a proper coloring with little communication. Previous work gave a deterministic $(2Δ-1)$-edge-coloring protocol using $O(n)$ bits, leaving open whether fewer colors can be obtained efficiently. We simultaneously reduce both the number of colors and the communication. For every fixed $\varepsilon>0$ and all sufficiently large $Δ$, we give a public-coin Las Vegas protocol that finds a proper $(1+\varepsilon)Δ$-edge coloring using $O(ne^{-γΔ} + 1)$ expected bits and $O\left(\frac{\log n}Δ+1\right)$ expected rounds, where $γ>0$ depends only on $\varepsilon$. Thus, the expected communication is $o(n)$ when $Δ=ω(1)$ and $O(1)$ when $Δ\ge C_\varepsilon\log n$, for a sufficiently large constant $C_\varepsilon$. Using only private coins adds $O(\log n)$ expected bits. Our key idea is a new randomized coloring procedure that allows Alice and Bob to color their edges using essentially the same color space with only a small amount of coordination, so most of their random choices remain private. To make this procedure succeed, we develop a communication-efficient constructive Lovász local lemma (LLL) for two parties. Our two-party constructive LLL is also of independent interest. We illustrate its broader applicability by applying it to standard LLL formulations of several other classical problems, obtaining communication-efficient two-party protocols.