Lower bounds for weighted matroid problems

DOI10.1145/3774814MaRDI QIDQ7299205zbMATH OpenFDO

Authors Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai

Publication date 17 July 2026

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3774814

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• A note on maximizing a submodular set function subject to a knapsack constraint
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• 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 knapsack problems with cardinality constraints
• Approximation Schemes for Multi-Budgeted Independence Systems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Connections in combinatorial optimization
• Dependent randomized rounding via exchange properties of combinatorial structures
• Fast Approximation Algorithms for Knapsack Problems
• Fixed-parameter tractability of maximum colored path and beyond
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• scientific article; zbMATH DE number 7788446 (Why is no real title available?)
• Matroid intersection algorithms
• Maximizing a monotone submodular function subject to a matroid constraint
• Minimum partition of a matroid into independent subsets
• Multi-budgeted matchings and matroid intersection via dependent rounding
• On bicriterion minimal spanning trees: An approximation
• On problems equivalent to \((\min,+)\)-convolution
• Random pseudo-polynomial algorithms for exact matroid problems
• The constrained minimum spanning tree problem
• The Multiple-Choice Knapsack Problem
• The random oracle hypothesis is false
• The random oracle methodology, revisited.
• There is no EPTAS for two-dimensional knapsack
• You (almost) can't beat brute force for 3-matroid intersection

This page was built for publication: Lower bounds for weighted matroid problems

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