Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property

DOI10.1007/978-3-030-79987-8_30OpenAlexW3174508056MaRDI QIDQ2115881

Soh Kumabe, Takanori Maehara

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79987-8_30

zbMATH Keywords

online algorithmknapsackprophet secretary problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of threshold stop rules and maximum for independent nonnegative random variables
• Improved online algorithms for Knapsack and GAP in the random order model
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
• A Knapsack Secretary Problem with Applications
• Semiamarts and finite values
• Online Contention Resolution Schemes
• Prophet Secretary Through Blind Strategies
• Prophet Secretary
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Comments on bases in dependence structures

This page was built for publication: Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property