Only recently progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))~(1/2))-competitive proc...
详细信息
ISBN:
(纸本)9781510813311
Only recently progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))~(1/2))-competitive procedure, and Lachish (2014) recently presented a O(log log(rank))-competitive algorithm. Both algorithms are involved with complex analyses. Using different tools, we present a considerably simpler O(log log(rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.
A sequence of objects that are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces cost...
详细信息
A sequence of objects that are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces costs. A reordering buffer, which is a random access buffer with storage capacity for k objects, can be used to rearrange this sequence online in such a way that the total costs are reduced. This concept is useful for many applications in computer science and *** strategy with the best-known competitive ratio is MAP. An upper bound of O(log k) on the competitive ratio of MAP is known and a nonconstant lower bound on the competitive ratio is not known. Based on theoretical considerations and experimental evaluations, we give strong evidence that the previously used proof techniques are not suitable to show an o(√log k) upper bound on the competitive ratio of MAP. However, we also give some evidence that in fact MAP achieves a competitive ratio of O(1).Further, we evaluate the performance of several strategies on random input sequences experimentally. MAP and its variants RC and RR clearly outperform the other strategies FIFO, LRU, and MCF. In particular, MAP, RC, and RR are the only known strategies whose competitive ratios do not depend on the buffer size. Furthermore, MAP achieves the smallest competitive ratio.
We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements with values, and needs to decide immediately and irrevocab...
详细信息
We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements with values, and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value. Hence, we study alternative performance measures. In particular, we suggest the Expectation of Ratio (or, in short, EoR), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant EoR implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the EoR is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. However, the probability of selecting the maximum does not generalize meaningfully to combinatorial constraints (beyond single-choice), since its direct equivalent is the probability of selecting an optimal overall set. We, thus, introduce the EoR as a cardinal variant of the probability of selecting the maximum, which extends naturally to combinatorial settings. Our main goal is to understand the relation between RoE and EoR in combinatorial settings. Specifically, we establish two reductions: for every feasibility constraint, the RoE and the EoR are at most a constant factor apart on worst case instances. Additionally, we show that the Eo
暂无评论