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

DOI10.4230/LIPICS.ICALP.2019.85OpenAlexW2965600716MaRDI QIDQ5091245

Eyal Mizrachi, Joachim Spoerhase, Sumedha Uniyal, Roy Schwartz

Publication date: 21 July 2022

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

zbMATH Keywords

coveringapproximation algorithmsubmodular functionpacking

Mathematics Subject Classification ID

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

Related Items (1)

Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing a class of submodular utility functions
• An efficient approximation for the generalized assignment problem
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Approximating the least core value and least core of cooperative games with supermodular costs
• Determinantal Point Processes for Machine Learning
• A threshold of ln n for approximating set cover
• Tight approximation algorithms for maximum general assignment problems
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Better Balance by Being Biased
• Reducibility among Combinatorial Problems
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Symmetry and Approximability of Submodular Maximization Problems
• Non-monotone submodular maximization under matroid and knapsack constraints
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

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