A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
From MaRDI portal
Publication:5091245
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
Related Items
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?
