Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint

DOI10.1137/16M1107644zbMath1421.90133arXiv1607.04527WikidataQ127369533 ScholiaQ127369533MaRDI QIDQ5232162

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

curvaturesubmodular functionknapsack constraints

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (12)

Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ 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 ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Cites Work

• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Fast algorithms for maximizing submodular functions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint