Submodular secretary problem with shortlists

DOI10.4230/LIPICS.ITCS.2019.1MaRDI QIDQ5090369zbMATH OpenFDO

Authors Shipra Agrawal, Mohammad Shadravan, Clifford Stein

Publication date 18 July 2022

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

zbMATH Keywords

secretary problemstreaming algorithmssubmodular optimization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Submodular secretary problems: cardinality, matching, and linear constraints
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• Submodular secretary problem and extensions
• Submodular secretary problem and extensions
• Improved competitive ratios for submodular secretary problems (extended abstract)

Cites work

• A dynamic near-optimal algorithm for online linear programming
• A multiple-choice secretary algorithm with applications to online auctions
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Dynamic Programming and Decision Theory
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• Improved algorithms and analysis for secretary problems and generalizations
• Maximizing Non-monotone Submodular Functions
• Online stochastic packing applied to display ad allocation
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Online submodular welfare maximization: greedy is optimal
• Optimal approximation for the submodular welfare problem in the value oracle model
• Optimal choice and assignment of the best \(m\) of \(n\) randomly arriving items
• Optimal time-critical scheduling via resource augmentation
• Speed is as powerful as clairvoyance
• Submodular maximization with cardinality constraints
• Submodular secretary problem and extensions
• Submodular secretary problems: cardinality, matching, and linear constraints
• The Optimal Choice of a Subset of a Population
• The submodular secretary problem goes linear
• Who solved the secretary problem

Cited in

(6)

• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Robust algorithms under adversarial injections
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Improved algorithms for maximum coverage in dynamic and random order streams

This page was built for publication: Submodular secretary problem with shortlists

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