Representative families for matroid intersections, with applications to location, packing, and covering problems

DOI10.1016/J.DAM.2021.03.014MaRDI QIDQ2028091zbMATH OpenOpenAlexFDO

Authors René van Bevern, Philipp Zschoche, O. Yu. Tsidulko

Publication date 31 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.11527

zbMATH Keywords

combinatorial optimizationmatroid paritymatroid medianmatroid set packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

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

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• A parameterized view on matroid optimization problems
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• Color-coding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Deterministic algorithms for matching and packing problems based on representative sets
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Facility Location with Matroid or Knapsack Constraints
• Facility location problems: a parameterized view
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Location science
• Matroid matching: the power of local search
• Maximizing a monotone submodular function subject to a matroid constraint
• Mixing Color Coding-Related Techniques
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Parameterized algorithms
• Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
• Reducibility among combinatorial problems
• Representative families of product families
• The power of local search: maximum coverage over a matroid
• Triangular Factorization and Inversion by Fast Matrix Multiplication

Cited in

(9)

• Centroids, Representations, and Submodular Flows
• 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

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)