Lower bounds for matroid optimization problems with a linear constraint
From MaRDI portal
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 AFPTAS for bin packing with partition matroid via a new method for LP rounding
- 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
- Budgeted matroid maximization: a parameterized viewpoint
- 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
This page was built for publication: Lower bounds for matroid optimization problems with a linear constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875144)
