Fractionally subadditive maximization under an incremental knapsack constraint

DOI10.1007/978-3-030-92702-8_13OpenAlexW3173650354MaRDI QIDQ2085751FDOQ2085751

Max Klimm, David Weckbecker, Y. 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

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

Cites Work

• A threshold of ln n for approximating set cover
• Stochastic on-line knapsack problems
• Combinatorial auctions with decreasing marginal utilities
• The online knapsack problem with incremental capacity
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
• An analysis of approximations for maximizing submodular set functions—I
• A General Approach for Incremental Approximation and Hierarchical Clustering
• Incremental network design with maximum flows
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• A note on maximizing a submodular set function subject to a knapsack constraint
• On Maximizing Welfare When Utility Functions Are Subadditive
• Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
• Algorithmic results for potential‐based flows: Easy and hard cases
• Robust Matchings
• Packing a Knapsack of Unknown Capacity
• Randomized strategies for cardinality robustness in the knapsack problem
• Computing knapsack solutions with cardinality robustness
• Robust matchings and matroid intersections
• Robust independence systems
• Robust monotone submodular function maximization
• Robust Randomized Matchings
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
• Optimization with demand oracles
• Incremental flow
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• General Bounds for Incremental Maximization
• Submodular Maximization with Uncertain Knapsack Capacity

Cited In (2)

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

This page was built for publication: Fractionally subadditive maximization under an incremental knapsack constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2085751)