Budgeted matroid maximization: a parameterized viewpoint

DOI10.4230/LIPICS.IPEC.2023.13MaRDI QIDQ6926197zbMATH OpenFDO

Authors Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.13

zbMATH Keywords

budgeted matchingbudgeted matroid intersectionFPT-approximation schemeknapsack problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A parameterized view on matroid optimization problems
• An EPTAS for budgeted matching and budgeted matroid intersection via representative sets
• An EPTAS for budgeted matroid independent set
• An FPTAS for budgeted laminar matroid independent set
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation Schemes for Multi-Budgeted Independence Systems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Budgeted matroid maximization: a parameterized viewpoint
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Deterministic algorithms for matching and packing problems based on representative sets
• Deterministic truncation of linear matroids
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Extremal combinatorics. With applications in computer science
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximations for k-exchange systems (extended abstract)
• Improved deterministic algorithms for weighted matching and packing problems
• Kernelization of packing problems
• Kernelization. Theory of parameterized preprocessing
• Limits and Applications of Group Algebras for Parameterized Problems
• Lossy kernelization
• Matroid matching and some applications
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Narrow sieves for parameterized paths and packings
• On Lagrangian relaxation for constrained maximization and reoptimization problems
• The constrained minimum spanning tree problem
• There is no EPTAS for two-dimensional knapsack

Cited in

(3)

• Lower bounds for matroid optimization problems with a linear constraint
• Budgeted matroid maximization: a parameterized viewpoint
• Sampling with a black box: faster parameterized approximation algorithms for vertex deletion problems

This page was built for publication: Budgeted matroid maximization: a parameterized viewpoint

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