Approximation algorithms in combinatorial scientific computing
From MaRDI portal
Publication:5230524
DOI10.1017/S0962492919000035zbMath1440.68337OpenAlexW2950905676MaRDI QIDQ5230524
Alex Pothen, S. M. Ferdous, Fredrik Manne
Publication date: 28 August 2019
Published in: Acta Numerica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0962492919000035
combinatorial optimizationapproximation algorithmsvertex-weighted matchingdegree-constrained subgraphscardinality matching\(b\)-edge coveredge-weighted \(b\)-matching, weighted edge coveredge-weighted matching
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex degrees (05C07)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Design and analysis of approximation algorithms
- Distributed algorithms for covering, packing and maximum weighted matching
- Blossom V: A new implementation of a minimum cost perfect matching algorithm
- Combinatorial algorithms for computing column space bases that have sparse inverses
- A simple approximation algorithm for the weighted matching problem
- On the use of optimal fractional matchings for solving the (integer) matching problem
- A fast approximation algorithm for the multicovering problem
- A polynomial algorithm for b-matchings: An alternative approach
- Zero knowledge and the chromatic number
- Predicting the structure of sparse orthogonal factors
- Weighted matching with vertex weights: An application to scheduling training sessions in NASA space shuttle cockpit simulators
- A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem
- Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A new pivoting strategy for Gaussian elimination
- Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Matching algorithms are fast in sparse random graphs
- Concerning nonnegative matrices and doubly stochastic matrices
- On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix
- Efficient Approximation Algorithms for Weighted $b$-Matching
- Bayesian Mechanism Design
- Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring
- A linear-time approximation algorithm for weighted matchings in graphs
- Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
- The university of Florida sparse matrix collection
- Design, implementation, and analysis of maximum transversal algorithms
- The Design of Approximation Algorithms
- Graph-Based Semi-Supervised Learning
- Linear-Time Approximation for Maximum Weight Matching
- Pivoting strategies for tough sparse indefinite systems
- Some Generalizations of the Problem of Distinct Representatives
- An Algorithm for a Minimum Cover of a Graph
- On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices
- New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
- Assignment Problems
- Solving matching problems with linear programming
- Predicting fill for sparse orthogonal factorization
- The Null Space Problem II. Algorithms
- A Greedy Heuristic for the Set-Covering Problem
- Computing the Minimum Fill-In is NP-Complete
- Odd Minimum Cut-Sets and b-Matchings
- A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
- Average-case analysis of algorithms for matchings and related problems
- Computing the block triangular form of a sparse matrix
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Data Structures for Weighted Matching and Extensions to b -matching and f -factors
- Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
- A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs
- Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
- A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
- A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs
- Algorithmics of Matching Under Preferences
- Engineering Algorithms for Approximate Weighted Matching
- Greedy in Approximation Algorithms
- SuperLU_DIST
- Implementing weighted b-matching algorithms
- Maximum matching and a polyhedron with 0,1-vertices
- An analysis of the stable marriage assignment algorithm
- Nested Dissection of a Regular Finite Element Mesh
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
- College Admissions and the Stability of Marriage
- The two possible values of the chromatic number of a random graph
