Approximation algorithms in combinatorial scientific computing. (1st May 2019)

• Record Type: Journal Article
• Authors: Pothen, Alex; Ferdous, S. M.; Manne, Fredrik
• Is Part Of: Acta numerica. Volume 28(2019)
• Page Start: 541
• Page End: 633
• Publication Date: 2019-05-01
• Subjects: Numerical analysis -- Periodicals; 518
• DOI: 10.1017/S0962492919000035
• Languages: English
• ISSNs: 0962-4929

Abstract

Abstract : We survey recent work on approximation algorithms for computing degree-constrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of cardinality matching, edge-weighted matching, vertex-weighted matching and edge-weighted $b$ -matching, and minimization versions of weighted edge cover and $b$ -edge cover. Exact algorithms for these problems are impractical for massive graphs with several millions of edges. For each problem we discuss theoretical foundations, the design of several linear or near-linear time approximation algorithms, their implementations on serial and parallel computers, and applications. Our focus is on practical algorithms that yield good performance on modern computer architectures with multiple threads and interconnected processors. We also include information about the software available for these problems.