scientific article; zbMATH DE number 7559044

DOI10.4230/LIPIcs.ITCS.2019.1MaRDI QIDQ5090369

Mohammad Shadravan, Shipra Agrawal, Clifford Stein

Publication date: 18 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

streaming algorithmssecretary problemsubmodular optimization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Optimal choice and assignment of the best \(m\) of \(n\) randomly arriving items
• Who solved the secretary problem
• Improved Algorithms and Analysis for Secretary Problems and Generalizations
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Submodular secretary problem and extensions
• Online Submodular Welfare Maximization
• Maximizing Non-monotone Submodular Functions
• Online Stochastic Packing Applied to Display Ad Allocation
• The Optimal Choice of a Subset of a Population
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Speed is as powerful as clairvoyance
• The Submodular Secretary Problem Goes Linear
• Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
• Submodular Maximization with Cardinality Constraints
• Dynamic Programming and Decision Theory
• Online submodular welfare maximization: Greedy is optimal
• Online submodular maximization: beating 1/2 made simple
• Optimal time-critical scheduling via resource augmentation

This page was built for publication: