7 papers
Improved Parallel Algorithms for EF1 Allocations
Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang +1
Allocating indivisible goods among agents is a fundamental task in fair division. Recent work of Garg and Psomas [AAMAS 2025] initiated the study of parallel algorithms for…
Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Guy Blelloch, Andrew Brady, Laxman Dhulipala +3
A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can…
Chamfer-Linkage for Hierarchical Agglomerative Clustering
Kishen N Gowda, Willem Fletcher, MohammadHossein Bateni +4
Hierarchical Agglomerative Clustering (HAC) is a widely-used clustering method based on repeatedly merging the closest pair of clusters, where inter-cluster distances are determine…
UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
Quinten De Man, Atharva Sharma, Kishen N Gowda +1
The dynamic trees problem is to maintain a tree under edge updates while supporting queries like connectivity queries or path queries. Despite the first data structure for this fun…
Parallel Hierarchical Agglomerative Clustering in Low Dimensions
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in based on repeatedly merging the closest p…
Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering
Quinten De Man, Laxman Dhulipala, Kishen N Gowda
Single-linkage clustering is a popular form of hierarchical agglomerative clustering (HAC) where the distance between two clusters is defined as the minimum distance between any pa…