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.

Fri 6 NovData Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
The gist
This paper studies how to spread tasks of different sizes across many machines so each machine does almost the same amount of work. Tasks can be split into smaller pieces assigned to different machines, but the goal is to keep the number of pieces per machine low. The authors focus on situations where there are more machines than tasks and find a simple, fast way to perfectly balance the load with the minimal number of task pieces per machine. This work improves on previous methods and helps systems where work is repeatedly redistributed across many processors.
Open → 2611.09267v1

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.

Thu 5 NovData Structures and Algorithms
The gist
The minimum bisection problem asks if a large network can be split into two equal parts with only a few connections crossing between them. The authors developed a new method that solves this problem much faster than before, using a clever way to count possible splits instead of just checking if one exists. They built a special structure that breaks the network into pieces that are hard to split further, allowing their method to work efficiently. This improvement may help solve similar problems in graph analysis more quickly.
Open → 2611.08202v1

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.

Tue 3 NovDiscrete Mathematics
The gist
This paper studies a type of network called a 3-uniform hypergraph, where each connection links exactly three nodes. It looks at how to color these connections so that no two touching connections share the same color, using as few colors as possible. The authors show that almost all such networks can be colored with a number of colors equal to their largest number of connections on a single node. This property, known for simpler networks, does not hold for more complex ones that link four or more nodes at a time.
Open → 2611.05622v1

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.

Wed 30 SeptDistributed, Parallel, and Cluster Computing
The gist
The paper addresses the problem of coloring edges in a network when the connections are split between two parties who want to coordinate with minimal communication. The authors develop a new method that allows them to color edges using almost the smallest possible number of colors while exchanging very few messages. Their method relies on a clever way to share random choices with little coordination using a two-party version of an important mathematical tool called the Lovász Local Lemma. This approach also works well for other problems that can be described using this lemma.
Open → 2609.39359v1