Fractionally subadditive maximization under an incremental knapsack constraint

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

zbMATH Keywords

competitive ratioknapsack constraintfractionally subadditiveincremental maximizationpotential-based flow

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows

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