Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint

DOI10.1137/16M1107644MaRDI QIDQ5232162zbMATH OpenWikidataFDO

Authors Yuichi Yoshida

Publication date 29 August 2019

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

Full work available at URL https://arxiv.org/abs/1607.04527

zbMATH Keywords

curvatureknapsack constraintssubmodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed $epsilon>0$, there exists a polynomial-time algorithm with an approximation ratio $1-c/e-epsilon$, where $cin[0,1]$ is the (total) curvature of the input function. This approximation ratio is tight up to $epsilon$ for any $cin[0,1]$. To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than $1-1/e$, which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio.

Recommendations

• Maximizing a monotone non-submodular function under a knapsack constraint
• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing submodular set functions subject to multiple linear constraints
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Cited in

(23)

• Maximizing expected utility over a knapsack constraint
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Generalized budgeted submodular set function maximization
• An almost optimal approximation algorithm for monotone submodular multiple knapsack
• Multi-pass streaming algorithms for monotone submodular function maximization
• Fractionally subadditive maximization under an incremental knapsack constraint
• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Maximizing a monotone non-submodular function under a knapsack constraint
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
• Finding the Maximum Subset with Bounded Convex Curvature
• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• Generalized budgeted submodular set function maximization
• Non-submodular maximization with matroid and knapsack constraints
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Per-round knapsack-constrained linear submodular bandits
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity
• Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• New approximations for monotone submodular maximization with knapsack constraint
• Submodular + supermodular function maximization with knapsack constraint
• Non-submodular maximization subject to a knapsack constraint on the integer lattice

This page was built for publication: Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint

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