Optimal stopping for many connected components in a graph

DOI10.1002/RSA.21000MaRDI QIDQ6074658zbMATH OpenOpenAlexFDO

Authors Michał Lasoń

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-treeconnected componentoptimal stopping

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: We study a new optimal stopping problem: Let $G$ be a fixed graph with $n$ vertices which become active on-line in time, one by another, in a random order. The active part of $G$ is the subgraph induced by the active vertices. Find a stopping algorithm that maximizes the expected number of connected components of the active part of $G$. We prove that if $G$ is a $k$-tree, then there is no asymptotically better algorithm than `wait until $frac1k+1$ fraction of vertices'. The maximum expected number of connected components equals to ${\displaystyle }$left(frac{k^k}{(k+1)^{k+1}}+o(1) ight)n.${\displaystyle }$

Recommendations

• Maximizing the expected number of components in an online search of a graph
• Optimal stopping in a search for a vertex with full degree in a random graph
• On randomized stopping points and perfect graphs
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• An optimal stopping problem on tree

Cites work

• An efficient algorithm for stopping on a sink in a directed graph
• Dynamic Programming and Decision Theory
• Dynamic threshold strategy for universal best choice problem
• From directed path to linear order -- the best choice problem for powers of directed path
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• scientific article; zbMATH DE number 67292 (Why is no real title available?)
• Maximizing the expected number of components in an online search of a graph
• On a universal best choice algorithm for partially ordered sets
• Partial-order analogue of the secretary problem: The binary tree case
• Partially ordered secretaries
• Percolation and best-choice problem for powers of paths
• Poisson approximation for large deviations
• Sum the odds to one and stop
• The best choice problem for upward directed graphs
• The best-choice problem for partially ordered objects.
• Who solved the secretary problem

Cited in

(3)

• Maximizing the expected number of components in an online search of a graph
• Hiring strategies
• Optimal stopping in a search for a vertex with full degree in a random graph

This page was built for publication: Optimal stopping for many connected components in a graph

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