Fractionally subadditive maximization under an incremental knapsack constraint

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

Authors: Y. Disser, Max Klimm, David Weckbecker 

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 (extended abstract)
• 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)