Fractionally subadditive maximization under an incremental knapsack constraint
From MaRDI portal
Publication:2085751
DOI10.1007/978-3-030-92702-8_13OpenAlexW3173650354MaRDI QIDQ2085751
Max Klimm, David Weckbecker, Yann Disser
Publication date: 19 October 2022
Full work available at URL: https://arxiv.org/abs/2106.14454
competitive ratioknapsack constraintfractionally subadditiveincremental maximizationpotential-based flow
Related Items (1)
Cites Work
- The online knapsack problem with incremental capacity
- Incremental network design with maximum flows
- A note on maximizing a submodular set function subject to a knapsack constraint
- Randomized strategies for cardinality robustness in the knapsack problem
- Robust monotone submodular function maximization
- Stochastic on-line knapsack problems
- Computing knapsack solutions with cardinality robustness
- Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
- Optimization with demand oracles
- Combinatorial auctions with decreasing marginal utilities
- Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
- A threshold of ln n for approximating set cover
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Incremental flow
- An analysis of approximations for maximizing submodular set functions—I
- Robust Matchings
- Structured Robust Submodular Maximization: Offline and Online Algorithms
- General Bounds for Incremental Maximization
- On Maximizing Welfare When Utility Functions Are Subadditive
- Robust Randomized Matchings
- Algorithmic results for potential‐based flows: Easy and hard cases
- Submodular Maximization with Uncertain Knapsack Capacity
- Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
- Packing a Knapsack of Unknown Capacity
- A General Approach for Incremental Approximation and Hierarchical Clustering
- Robust Matchings and Matroid Intersections
- Robust Independence Systems
This page was built for publication: Fractionally subadditive maximization under an incremental knapsack constraint
