Fractionally Subadditive Maximization under an Incremental Knapsack Constraint

No abstract is available for this paper.

• Publication year

  2021

• Venue

  Workshop on Approximation and Online Algorithms

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-030-92702-8_13
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Unified greedy approximability beyond submodular maximization

  2020cited by this paper
• Algorithmic results for potential‐based flows: Easy and hard cases

  2018cited by this paper
• Submodular Maximization with Uncertain Knapsack Capacity

  2018cited by this paper
• General bounds for incremental maximization

  2017influential reference
• Structured Robust Submodular Maximization: Offline and Online Algorithms

  2017cited by this paper
• Randomized strategies for cardinality robustness in the knapsack problem

  2017cited by this paper
• Online knapsack of unknown capacity: How to optimize energy consumption in smartphones

  2017cited by this paper
• Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint

  2016cited by this paper
• Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design

  2016cited by this paper
• Robust monotone submodular function maximization

  2015cited by this paper
• The online knapsack problem with incremental capacity

  2015cited by this paper
• Robust randomized matchings

  2015cited by this paper
• Packing a Knapsack of Unknown Capacity

  2013cited by this paper
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints

  2013cited by this paper
• Computing knapsack solutions with cardinality robustness

  2011cited by this paper
• Optimization with Demand Oracles

  2011cited by this paper
• Robust Independence Systems

  2011cited by this paper
• Robust Matchings and Matroid Intersections

  2010cited by this paper
• Incremental flow

  2007cited by this paper
• An improved approximation algorithm for combinatorial auctions with submodular bidders

  2006cited by this paper
• On maximizing welfare when utility functions are subadditive

  2006cited by this paper
• A general approach for incremental approximation and hierarchical clustering

  2006cited by this paper
• A note on maximizing a submodular set function subject to a knapsack constraint

  2004cited by this paper
• Robust Matchings

  2002influential reference
• Combinatorial auctions with decreasing marginal utilities

  2001cited by this paper
• Bidding and allocation in combinatorial auctions

  2000cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Stochastic on-line knapsack problems

  1995cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper
• European Journal of Operational Research Incremental Network Design with Maximum Flows

  year unknowncited by this paper

• Incremental Maximization via Continuization

  2023cites this paper
• Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

  2022cites this paper
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows

  2021cites this paper