Submodular secretary problem and extensions

DOI10.1145/2500121MaRDI QIDQ2933663zbMATH OpenOpenAlexFDO

Authors MohammadHossein Bateni, Morteza Zadimoghaddam, Mohammad T. Hajiaghayi

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/51336

zbMATH Keywords

competitive algorithmsknapsack constraintmatroid constraintonline algorithmssecretary problemstopping theorysubmodular

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Submodular secretary problem and extensions
• Submodular secretary problems: cardinality, matching, and linear constraints
• Matroids, secretary problems, and online mechanisms
• The submodular secretary problem goes linear
• Matroid Secretary Problems

Cited in

(35)

• Know when to persist: deriving value from a stream buffer
• Secretary markets with local information
• Online algorithms for the maximum \(k\)-interval coverage problem
• Monotone k-submodular secretary problems: cardinality and knapsack constraints
• Fair allocation of indivisible goods: beyond additive valuations
• Know when to persist: deriving value from a stream buffer (extended abstract)
• Secretary problems with convex costs
• The simulated greedy algorithm for several submodular matroid secretary problems
• Revenue submodularity
• Improved competitive ratios for submodular secretary problems (extended abstract)
• Streaming algorithms for submodular function maximization
• Secretary markets with local information
• Submodular secretary problem and extensions
• Building a good team: secretary problems and the supermodular degree
• Combinatorial prophet inequalities
• A framework for the secretary problem on the intersection of matroids
• Secretary problems: weights and discounts
• The submodular secretary problem goes linear
• Online submodular maximization with preemption
• Strong algorithms for the ordinal matroid secretary problem
• Submodular secretary problems: cardinality, matching, and linear constraints
• Maximizing profit with convex costs in the random-order model
• A Framework for the Secretary Problem on the Intersection of Matroids
• Submodular secretary problem with shortlists
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Prophet secretary
• Online contention resolution schemes with applications to Bayesian selection problems
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• Algorithms for maximizing monotone submodular function minus modular function under noise
• Online budget-feasible mechanism design with predictions
• Matroid secretary via labeling schemes
• Budget-feasible mechanism design: simpler, better mechanisms and general payment constraints
• Beating competitive ratio 4 for graphic matroid secretary
• Online happiness maximization queries
• Simultaneous selection

This page was built for publication: Submodular secretary problem and extensions

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