A Parallel Approximation Algorithm for Maximizing Submodular b-Matching

被引：0

作者：

Ferdous, S. M. ^{[1
]}

Pothen, Alex ^{[1
]}

Khan, Arif ^{[2
]}

Panyala, Ajay ^{[3
]}

Halappanavar, Mahantesh ^{[2
]}

机构：

[1] Purdue Univ, Comp Sci Dept, W Lafayette, IN 47907 USA

[2] Pacific Northwest Natl Lab, Data Sci & Machine Intelligence, Richland, WA 99352 USA

[3] Pacific Northwest Natl Lab, High Performance Comp, Richland, WA 99352 USA

来源：

PROCEEDINGS OF THE 2021 SIAM CONFERENCE ON APPLIED AND COMPUTATIONAL DISCRETE ALGORITHMS, ACDA21 | 2021年

关键词：

FUNCTION SUBJECT;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：45 / 56

页数：12

共 37 条

[11] The University of Florida Sparse Matrix Collection [J].

Davis, Timothy A. ;

Hu, Yifan .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2011, 38 (01)

[12]

Dickerson JP, 2019, AAAI CONF ARTIF INTE, P1877

[13] A simple approximation algorithm for the weighted matching problem [J].

Drake, DE ;

Hougardy, S .

INFORMATION PROCESSING LETTERS, 2003, 85 (04) :211-213

[14] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[15]

Feldman M, 2011, LECT NOTES COMPUT SC, V6942, P784, DOI 10.1007/978-3-642-23719-5_66

[16]

FISHER ML, 1978, MATH PROGRAM STUD, V8, P73, DOI 10.1007/BFb0121195

[17] Faster approximation algorithms for maximizing a monotone submodular function subject to a b-matching constraint [J].

Fujii, Kaito .

INFORMATION PROCESSING LETTERS, 2016, 116 (09) :578-584

[18] NEW VARIATIONS IN 2-ELECTRON INTEGRAL EVALUATION IN THE CONTEXT OF DIRECT SCF PROCEDURES [J].

HAMILTON, TP ;

SCHAEFER, HF .

CHEMICAL PHYSICS, 1991, 150 (02) :163-171

[19] EFFICIENT APPROXIMATION ALGORITHMS FOR WEIGHTED b-MATCHING [J].

Khan, Arif ;

Pothen, Alex ;

Patwary, Md. Mostofa Ali ;

Satish, Nadathur Rajagopalan ;

Sundaram, Narayanan ;

Manne, Fredrik ;

Halappanavar, Mahantesh ;

Dubey, Pradeep .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2016, 38 (05) :S593-S619

[20] From NWChem to NWChemEx: Evolving with the Computational Chemistry Landscape [J].

Kowalski, Karol ;

Bair, Raymond ;

Bauman, Nicholas P. ;

Boschen, Jeffery S. ;

Bylaska, Eric J. ;

Daily, Jeff ;

de Jong, Wibe A. ;

Dunning, Thom, Jr. ;

Govind, Niranjan ;

Harrison, Robert J. ;

Keceli, Murat ;

Keipert, Kristopher ;

Krishnamoorthy, Sriram ;

Kumar, Suraj ;

Mutlu, Erdal ;

Palmer, Bruce ;

Panyala, Ajay ;

Peng, Bo ;

Richard, Ryan M. ;

Straatsma, T. P. ;

Sushko, Peter ;

Valeev, Edward F. ;

Valiev, Marat ;

van Dam, Hubertus J. J. ;

Waldrop, Jonathan M. ;

Williams-Young, David B. ;

Yang, Chao ;

Zalewski, Marcin ;

Windus, Theresa L. .

CHEMICAL REVIEWS, 2021, 121 (08) :4962-4998

← 1 2 3 4 →