Two-stage submodular maximization under knapsack and matroid constraints

DOI10.1007/978-3-031-20350-3_13MaRDI QIDQ6111952

Xiaoyan Zhang, Zhi-cheng Liu, Dong-lei Du, Jing Jin

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

submodular functionmatroidknapsack constraint

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Inapproximability results for combinatorial auctions with submodular utility functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A constrained two-stage submodular maximization
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Online submodular maximization: beating 1/2 made simple

This page was built for publication: Two-stage submodular maximization under knapsack and matroid constraints