Online independent set beyond the worst-case: secretaries, prophets, and periods

DOI10.1007/978-3-662-43951-7_43MaRDI QIDQ5167865zbMATH OpenOpenAlexFDO

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

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

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

Abstract: We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applications to, e.g., task scheduling and spectrum allocation. In the online setting, it is assumed that nodes of an unknown graph arrive one by one over time. An online algorithm has to decide whether an arriving node should be included into the independent set. Unfortunately, this natural and practically relevant online problem cannot be studied in a meaningful way within a classical competitive analysis as the competitive ratio on worst-case input sequences is lower bounded by $Omega(n)$. As a worst-case analysis is pointless, we study online independent set in a stochastic analysis. Instead of focussing on a particular stochastic input model, we present a generic sampling approach that enables us to devise online algorithms achieving performance guarantees for a variety of input models. In particular, our analysis covers stochastic input models like the secretary model, in which an adversarial graph is presented in random order, and the prophet-inequality model, in which a randomly generated graph is presented in adversarial order. Our sampling approach bridges thus between stochastic input models of quite different nature. In addition, we show that our approach can be applied to a practically motivated admission control setting. Our sampling approach yields an online algorithm for maximum independent set with competitive ratio $O(h{o}^2)$ with respect to all of the mentioned stochastic input models. for graph classes with inductive independence number $ho$. The approach can be extended towards maximum-weight independent set by losing only a factor of $O(logn)$ in the competitive ratio with $n$ denoting the (expected) number of nodes.

Recommendations

• Online independent sets.
• scientific article; zbMATH DE number 1696636
• Matroid Secretary Problems
• scientific article; zbMATH DE number 5842466
• Algorithms for Secretary Problems on Graphs and Hypergraphs

Cited in

(28)

• Competitive algorithms for multistage online scheduling
• Online independent sets.
• Secretary markets with local information
• Dynamic node packing
• The secretary recommendation problem
• Prophet inequalities vs. approximating optimum online
• Prior independent mechanisms via prophet inequalities with limited information
• From pricing to prophets, and back!
• Network design under general wireless interference
• scientific article; zbMATH DE number 1696636 (Why is no real title available?)
• On-line models and algorithms for max independent set
• Secretary markets with local information
• The Temp Secretary Problem
• Online appointment scheduling in the random order model
• Spanning trees with edge conflicts and wireless connectivity
• A Framework for the Secretary Problem on the Intersection of Matroids
• Packing returning secretaries
• Hiring secretaries over time: the benefit of concurrent employment
• Effective Wireless Scheduling via Hypergraph Sketches
• Packing returning secretaries
• Stochastic input models for online computing
• Online class cover problem
• Prophet secretary for combinatorial auctions and matroids
• Competitive analysis with a sample and the secretary problem
• Simple and optimal online contention resolution schemes for k-uniform matroids
• Stable approximation algorithms for dominating set and independent set
• Random-order online independent set of intervals and hyperrectangles
• Beating competitive ratio 4 for graphic matroid secretary

This page was built for publication: Online independent set beyond the worst-case: secretaries, prophets, and periods

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