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

DOI10.1137/23m1569265OpenAlexW4391565251MaRDI QIDQ6202753

David Weckbecker, Annette Lutz, Yann Disser, Max Klimm

Publication date: 27 February 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/23m1569265

zbMATH Keywords

competitive analysisflowincremental optimizationfractional subadditivity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Online algorithms; streaming algorithms (68W27) Robustness in mathematical programming (90C17)

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
• Fractionally subadditive maximization under an incremental knapsack constraint
• General bounds for incremental maximization
• 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
• A threshold of ln n for approximating set cover
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• 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
• 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
• Unified greedy approximability beyond submodular maximization

This page was built for publication: Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows