Approximate generalized matching: f-matchings and f-edge covers

DOI10.1007/S00453-022-00949-5MaRDI QIDQ2149100zbMATH OpenOpenAlexFDO

Authors Dawei Huang, Seth Pettie

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.05761

zbMATH Keywords

matchingedge coversf-factors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper we present linear time approximation schemes for several generalized matching problems on nonbipartite graphs. Our results include $O_{e}psilon(m)$-time algorithms for $(1-epsilon)$-maximum weight $f$-factor and $(1+epsilon)$-approximate minimum weight $f$-edge cover. As a byproduct, we also obtain direct algorithms for the exact cardinality versions of these problems running in $O(msqrtf(V))$ time. The technical contributions of this work include an efficient method for maintaining {em relaxed complementary slackness} in generalized matching problems and approximation-preserving reductions between the $f$-factor and $f$-edge cover problems.

Recommendations

• Linear-time approximation for maximum weight matching
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Faster scaling algorithms for general graph matching problems
• Algorithms for weighted matching generalizations. I: Bipartite graphs, \(b\)-matching, and unweighted \(f\)-factors
• scientific article; zbMATH DE number 1304326

Cites work

• scientific article; zbMATH DE number 1953187 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time algorithm for a special case of disjoint set union
• A simple approximation algorithm for the weighted matching problem
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Combinatorial optimization. Networks and matroids
• Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster Scaling Algorithms for Network Problems
• Faster scaling algorithms for general graph matching problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear-time approximation for maximum weight matching
• Maximum matching and a polyhedron with 0,1-vertices
• On the Problem of Decomposing a Graph into n Connected Factors
• Paths, Trees, and Flowers
• Scaling algorithms for weighted matching in general graphs

Cited in

(6)

• A weight-scaling algorithm for \(f\)-factors of multigraphs
• Blocking trails for \(f\)-factors of multigraphs
• Approximation algorithms in combinatorial scientific computing
• Approximability of Edge Matching Puzzles
• Approximate core allocations for edge cover games
• FPTAS for counting weighted edge covers

This page was built for publication: Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149100)