Improved approximation for 3-dimensional matching via bounded pathwidth local search

DOI10.1109/FOCS.2013.61MaRDI QIDQ6981724zbMATH OpenFDO

Authors Marek Cygan

Publication date 20 May 2025

Full work available at URL https://doi.org/10.1109/FOCS.2013.61

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(12)

• Maximum common induced subforests and minimum common induced superforests of a set of forests
• Online matching on 3-uniform hypergraphs
• Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
• Approximate hypergraph vertex cover and generalized Tuza's conjecture
• Hypergraph representation via axis-aligned point-subspace cover
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• Almost tight bounds for online hypergraph matching
• An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs
• A \(\frac{4}{3}\)-approximation for the maximum leaf spanning arborescence problem in DAGs
• Complexity and approximation algorithms for fixed charge transportation problems
• Semi-streaming algorithms for hypergraph matching
• Complexity and approximation algorithms for fixed charge transportation problems

This page was built for publication: Improved approximation for 3-dimensional matching via bounded pathwidth local search

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