FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

DOI10.1137/21m1442267arXiv2011.06268OpenAlexW4287599529MaRDI QIDQ6100609

Chien-Chung Huang, Justin Ward

Publication date: 22 June 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

submodular functionFPTstreaming\(\ell\)-matchoid

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Optimization with uniform size queries
• On matroid parity and matching polytopes
• Submodular maximization meets streaming: matchings, matroids, and more
• Computing small partial coverings
• A parameterized view on matroid optimization problems
• Matching theory
• New hash functions and their use in authentication and set equality
• FPT approximation schemes for maximizing submodular functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Better streaming algorithms for the maximum coverage problem
• Limitations of randomized mechanisms for combinatorial auctions
• Matroid Matching: The Power of Local Search
• Streaming Kernelization
• Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems
• A threshold of ln n for approximating set cover
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Streaming Algorithms for Submodular Function Maximization
• Deterministic Truncation of Linear Matroids
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Complexity of Matroid Property Algorithms
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Color-coding
• Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
• Reducibility among Combinatorial Problems
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Towards a theory of parameterized streaming algorithms
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Linear representation of transversal matroids and gammoids parameterized by rank
• Semi-streaming algorithms for submodular matroid intersection

This page was built for publication: FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective