FPT approximation schemes for maximizing submodular functions
From MaRDI portal
Publication:1680508
DOI10.1016/j.ic.2017.10.002zbMath1380.68449arXiv1510.00215OpenAlexW2766474417MaRDI QIDQ1680508
Publication date: 16 November 2017
Published in: Information and Computation, Web and Internet Economics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.00215
matchingfixed parameter tractabilityapproximation algorithmscomputational social choiceparameterized complexity
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Social choice (91B14)
Related Items (5)
FPT approximation schemes for maximizing submodular functions ⋮ Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Interactive optimization of submodular functions under matroid constraints ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- A note on maximizing a submodular set function subject to a knapsack constraint
- FPT approximation schemes for maximizing submodular functions
- Justified representation in approval-based committee voting
- On the complexity of achieving proportional representation
- Parametrized complexity theory.
- Approval Balloting for Multi-winner Elections
- Computational Aspects of Approval Voting
- On the Computation of Fully Proportional Representation
- Maximizing Non-monotone Submodular Functions
- A threshold of ln n for approximating set cover
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Optimal Value of Information in Graphical Models
- A Greedy Heuristic for the Set-Covering Problem
- An analysis of approximations for maximizing submodular set functions—I
- Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
- Non-monotone submodular maximization under matroid and knapsack constraints
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Parameterized Algorithms
This page was built for publication: FPT approximation schemes for maximizing submodular functions
