Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints

DOI10.1016/j.tcs.2022.04.003OpenAlexW4226115741MaRDI QIDQ2140573

Zhongzheng Tang, Hau Chan, Chen-Hao Wang

Publication date: 23 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.003

zbMATH Keywords

submodularitycompetitive ratioonline algorithmsecretary problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Maximization of \(k\)-submodular function with a matroid constraint ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization

Cites Work

• Unnamed Item
• Unnamed Item
• The simulated greedy algorithm for several submodular matroid secretary problems
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• Submodular secretary problem and extensions
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Towards Minimizing k-Submodular Functions
• Primal Beats Dual on Online Packing LPs in the Random-Order Model
• Improved Approximation Algorithms for k-Submodular Function Maximization
• The Submodular Secretary Problem Goes Linear
• Maximizing k -Submodular Functions and Beyond
• Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
• Improved Randomized Algorithm for k-Submodular Function Maximization

This page was built for publication: Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints