  We design new serial and parallel approximation algorithms for computing a
maximum weight $b$-matching in an edge-weighted graph with a submodular
objective function. This problem is NP-hard; the new algorithms have
approximation ratio $1/3$, and are relaxations of the Greedy algorithm that
rely only on local information in the graph, making them parallelizable. We
have designed and implemented Local Lazy Greedy algorithms for both serial and
parallel computers. We have applied the approximate submodular $b$-matching
algorithm to assign tasks to processors in the computation of Fock matrices in
quantum chemistry on parallel computers. The assignment seeks to reduce the run
time by balancing the computational load on the processors and bounding the
number of messages that each processor sends. We show that the new assignment
of tasks to processors provides a four fold speedup over the currently used
assignment in the NWChemEx software on $8000$ processors on the Summit
supercomputer at Oak Ridge National Lab.

Data Structures and Algorithms;Distributed, Parallel, and Cluster Computing