Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods

DOI10.1007/978-3-662-43951-7_43zbMath1409.68342arXiv1307.3192OpenAlexW1499357532MaRDI QIDQ5167865

Thomas Kesselheim, Oliver Göbel, Berthold Vöcking, Martin Hoefer, Thomas Schleiden

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)

Related Items (17)

Secretary Markets with Local Information ⋮ The Temp Secretary Problem ⋮ Online Appointment Scheduling in the Random Order Model ⋮ The secretary recommendation problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Network design under general wireless interference ⋮ Prophet inequalities vs. approximating optimum online ⋮ Packing returning secretaries ⋮ Hiring Secretaries over Time: The Benefit of Concurrent Employment ⋮ Spanning Trees With Edge Conflicts and Wireless Connectivity ⋮ Competitive algorithms for multistage online scheduling ⋮ Secretary markets with local information ⋮ Unnamed Item ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ From pricing to prophets, and back! ⋮ Effective Wireless Scheduling via Hypergraph Sketches ⋮ Dynamic node packing

This page was built for publication: Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods