A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

DOI10.4230/LIPICS.ICALP.2019.85MaRDI QIDQ5091245zbMATH OpenOpenAlexFDO

Authors Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, Sumedha Uniyal

Publication date 21 July 2022

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

zbMATH Keywords

approximation algorithmcoveringpackingsubmodular function

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Efficient Submodular Function Maximization under Linear Packing Constraints
• Fast algorithms for maximizing submodular functions
• Maximizing submodular set functions subject to multiple linear constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Non-monotone submodular maximization under matroid and knapsack constraints

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• An efficient approximation for the generalized assignment problem
• Approximating the least core value and least core of cooperative games with supermodular costs
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
• Combinatorial approximation algorithms for the maximum directed cut problem
• Determinantal point processes for machine learning
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3559283 (Why is no real title available?)
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a class of submodular utility functions
• Non-monotone submodular maximization under matroid and knapsack constraints
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Reducibility among combinatorial problems
• Revenue submodularity
• Some optimal inapproximability results
• Symmetry and Approximability of Submodular Maximization Problems
• The budgeted maximum coverage problem
• Tight approximation algorithms for maximum general assignment problems

Cited in

(3)

• Efficient Submodular Function Maximization under Linear Packing Constraints
• A Tight Bound for Stochastic Submodular Cover
• Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid

This page was built for publication: A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

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