FPT-Algorithms for the -Matchoid Problem with a Coverage Objective

DOI10.1137/21M1442267MaRDI QIDQ6100609zbMATH OpenOpenAlexFDO

Authors 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

\(\ell\)-matchoidFPTstreamingsubmodular function

Mathematics Subject Classification ID

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

Abstract: We consider the problem of optimizing a coverage function under a $ell$-matchoid of rank $k$. We design fixed-parameter algorithms as well as streaming algorithms to compute an exact solution. Unlike previous work that presumes linear representativity of matroids, we consider the general oracle model. For the special case where the coverage function is linear, we give a deterministic fixed-parameter algorithm parameterized by $ell$ and $k$. This result, combined with the lower bounds of Lovasz, and Jensen and Korte demonstrates a separation between the $ell$-matchoid and the matroid $ell$-parity problems in the setting of fixed-parameter tractability. For a general coverage function, we give both deterministic and randomized fixed-parameter algorithms, parameterized by $ell$ and $z$, where $z$ is the number of points covered in an optimal solution. The resulting algorithms can be directly translated into streaming algorithms. For unweighted coverage functions, we show that we can find an exact solution even when the function is given in the form of a value oracle (and so we do not have access to an explicit representation of the set system). Our result can be implemented in the streaming setting and stores a number of elements depending only on $ell$ and $z$, but completely indpendent of the total size $n$ of the ground set. This shows that it is possible to circumvent the recent space lower bound of Feldman et al, by parameterizing the solution value. This result, combined with existing lower bounds, also provides a new separation between the space and time complexity of maximizing an arbitrary submodular function and a coverage function in the value oracle model.

Cites work

• A parameterized view on matroid optimization problems
• A threshold of ln n for approximating set cover
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Better streaming algorithms for the maximum coverage problem
• Chamberlin-Courant rule with approval ballots: approximating the MaxCover problem with bounded frequencies in FPT time
• Color-coding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Computing small partial coverings
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 7758364 (Why is no real title available?)
• Improved algorithms for path, matching, and packing problems
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Limitations of randomized mechanisms for combinatorial auctions
• Linear representation of transversal matroids and gammoids parameterized by rank
• Matching theory
• Matroid matching: the power of local search
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• New hash functions and their use in authentication and set equality
• On matroid parity and matching polytopes
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Optimization with uniform size queries
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Quasipolynomial representation of transversal matroids with applications in parameterized complexity
• Reducibility among combinatorial problems
• Semi-streaming algorithms for submodular matroid intersection
• Streaming algorithms for submodular function maximization
• Streaming kernelization
• Submodular maximization over multiple matroids via generalized exchange properties
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Towards a theory of parameterized streaming algorithms

Cited in

(4)

• Budgeted matroid maximization: a parameterized viewpoint
• Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries
• Polynomial kernels with reachability for weighted d-matroid intersection
• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem

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

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