Algorithms for Secretary Problems on Graphs and Hypergraphs
From MaRDI portal
Publication:5321681
DOI10.1007/978-3-642-02930-1_42zbMath1248.68573OpenAlexW2113654320MaRDI QIDQ5321681
Publication date: 14 July 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02930-1_42
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)
Related Items (33)
The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Secretary Markets with Local Information ⋮ Online crowdsourced truck delivery using historical information ⋮ The Temp Secretary Problem ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Online network design with outliers ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ A note on the online interval scheduling secretary problem ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ Constant-competitiveness for random assignment matroid secretary without knowing the matroid ⋮ Packing returning secretaries ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Secretary and online matching problems with machine learned advice ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Competitive weighted matching in transversal matroids ⋮ Matroid prophet inequalities and applications to multi-dimensional mechanism design ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ The Submodular Secretary Problem Goes Linear ⋮ Buyback Problem - Approximate Matroid Intersection with Cancellation Costs ⋮ Stable secretaries ⋮ Online stochastic matching: new algorithms and bounds ⋮ Secretary markets with local information ⋮ On variants of the matroid secretary problem ⋮ Unnamed Item ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids ⋮ A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item ⋮ Online generalized assignment problem with historical information
This page was built for publication: Algorithms for Secretary Problems on Graphs and Hypergraphs
