Representative families for matroid intersections, with applications to location, packing, and covering problems
From MaRDI portal
Publication:2028091
DOI10.1016/J.DAM.2021.03.014zbMATH Open1469.90125arXiv1806.11527OpenAlexW3134250307MaRDI QIDQ2028091FDOQ2028091
Authors: René van Bevern, Philipp Zschoche, O. Yu. Tsidulko 
Publication date: 31 May 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
Full work available at URL: https://arxiv.org/abs/1806.11527
Recommendations
- Representative families: a unified tradeoff-based approach
- Representative families: a unified tradeoff-based approach
- Efficient computation of representative families with applications in parameterized and exact algorithms
- A parameterized view on matroid optimization problems
- A Parameterized View on Matroid Optimization Problems
Cites Work
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Title not available (Why is that?)
- Mixing Color Coding-Related Techniques
- Color-coding
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Parameterized algorithms
- Maximizing a monotone submodular function subject to a matroid constraint
- Title not available (Why is that?)
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Deterministic algorithms for matching and packing problems based on representative sets
- Facility location problems: a parameterized view
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- A parameterized view on matroid optimization problems
- Location science
- Facility Location with Matroid or Knapsack Constraints
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Representative families of product families
- Matroid matching: the power of local search
- The power of local search: maximum coverage over a matroid
- Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
- Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
- Improved approximation algorithms for matroid and knapsack median problems and applications
Cited In (9)
- Covering intersecting bi-set families under matroid constraints
- The matroid intersection cover problem
- Fast approximation of matroid packing and covering
- Representative families: a unified tradeoff-based approach
- Constrained hitting set problem with intervals
- A faster parameterized algorithm for temporal matching
- A parameterized view on matroid optimization problems
- Representative families: a unified tradeoff-based approach
- Centroids, Representations, and Submodular Flows
This page was built for publication: Representative families for matroid intersections, with applications to location, packing, and covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028091)
