This is the companion codebase of the publication:
S M Ferdous, Alex Pothen, Arif Khan, Ajay Panyala, and Mahantesh Halappanavar, “A parallel approximation algorithm for submodular b-matching,” in Proceedings of the First SIAM Conference on Applied and Computational Discrete Algorithms (ACDA), SIAM, 2021. DOI: 10.1137/1.9781611976830.5.
Here is the arXiv Link of the publication.
We design new serial and parallel approximation algorithms for computing a maximum weight
The default compiler is GNU. Other compilers may also be used using standard CMAKE options. This software requires OpenMP support.
- clone the repository to a local directory (say submodular-matching)
git clone https://github.com/smferdous1/Submodular-b-matching.git submodular-matching
- move to the local repository
cd submodular-matching
- create a "build" directory and move to the directory
mkdir build && cd build
- run cmake to the upper directory
cmake ..
- run make
make
This software package implements the serial and parallel local lazy greedy algorithm for maximizing submodular functions subject to b-matching constraints. A b-matching is a
subgraph where each vertex has degree at most an integer
$Z = \sum_{v \in V} \left(\sum_{e \in \delta(v)}{W(e)x(e)}\right)^\alpha.$ Here$x(e)$ is the characteristic function of the matching, i.e.,$x(e) = 1$ if the edge,$e$ belongs to the b-matching.$\alpha$ is between 0 to 1 and controls the concavity. If$\alpha = 1$ , the function becomes linear.
The "src" directory contains necessary library functions for the lazy greedy, serial and shared memory local lazy greedy, and load balancing functions. The "tests" directory contains the test and application files.
src/submodularGreedybMatching.cpp
src/localLazyGreed.cpp
src/shmLocalLazyGreedy.cpp
One application of submodular b-matching is to generate load balancing assignment of blocks of Fock matrices to the multiprocessors. We provide two implementations of such assignments. In "tests/load_balance_test.cpp" files, we use the default lazy greedy to generate the assignments. Since the input graph here is a complete graph, this implementation is slow. Hence, we provide a direct implementation of the load balancing assignment that generates the same matching as using the lazy greedy in "src/loadBalSimple.cpp" and the application file in"tests/load_balance_test_simple.cpp".