A 43-approximation for the maximum leaf spanning arborescence problem in DAGs

DOI10.1007/S10107-025-02233-0MaRDI QIDQ7239184zbMATH OpenFDO

Authors Meike Neuwohner

Publication date 8 May 2026

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-025-02233-0

zbMATH Keywords

hereditary set packinglocal searchmaximum leaf spanning arborescence problemweighted set packing

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• A 4/3-approximation for the maximum leaf spanning arborescence problem in DAGs
• A greedy approximation for minimum connected dominating sets
• A short note on the approximability of the maximum leaves spanning tree problem
• An approximation algorithm for the maximum leaf spanning arborescence problem
• An improved approximation for maximum weighted \(k\)-set packing
• Approximating the k-set packing problem by local improvements
• Approximation algorithms for connected dominating sets
• Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
• How heavy independent sets help to find arborescences with many leaves in DAGs
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Improved approximation for 3-dimensional matching via bounded pathwidth local search
• Kernel(s) for problems with no kernel
• Leafy spanning arborescences in DAGs
• Max-leaves spanning tree is APX-hard for cubic graphs
• Maximum matching and a polyhedron with 0,1-vertices
• Non-approximability results for optimization problems on bounded degree instances
• On finding directed trees with many leaves
• On Syntactic versus Computational Views of Approximability
• Passing the limits of pure local search for weighted \(k\)-Set packing
• Spanning directed trees with many leaves
• The limits of local search for weighted k-set packing

This page was built for publication: A \(\frac{4}{3}\)-approximation for the maximum leaf spanning arborescence problem in DAGs

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