Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141693 | Discrete Optimization | 2010 | 8 Pages |
Abstract
We consider the following online decision problem. The vertices of a directed path are being observed one by one in some random order by a selector. At time tt the selector examines the ttth vertex and knows the graph induced by the tt vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that it belongs to some prescribed subset of vertices. The optimal stopping time for a subset consisting of the two top vertices is given. For the path of cardinality nn the numerical approximation of the probability of the right choice according to the optimal algorithm is given.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Michał Przykucki, Małgorzata Sulkowska,