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

DOI10.1007/S00453-022-00949-5zbMATH Open1492.68144arXiv1706.05761OpenAlexW4214659657MaRDI QIDQ2149100FDOQ2149100

Dawei Huang, Seth Pettie

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• A Greedy Heuristic for the Set-Covering Problem
• Paths, Trees, and Flowers
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On the Problem of Decomposing a Graph into n Connected Factors
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Maximum matching and a polyhedron with 0,1-vertices
• A linear-time algorithm for a special case of disjoint set union
• Linear-Time Approximation for Maximum Weight Matching
• 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
• Combinatorial optimization. Networks and matroids
• Data Structures for Weighted Matching and Extensions to b -matching and f -factors
• Scaling Algorithms for Weighted Matching in General Graphs

Cited In (5)

• 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

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)