اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLower Bounds for Bruss Odds Problem with Multiple Stoppings
246
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We give asymptotic lower bounds of the value for Bruss optimal stopping problem with multiple stopping chances. It interestingly consists of the asymptotic threshold values in the optimal multiple stopping strategy. Another interesting implication of the result is that the asymptotic value for each secretary problem with multiple stoppings is in fact a typical lower bound in a much more general class of multiple stopping problems as modifications of odds problem.
قيم البحث
اقرأ أيضاً
Let $(X, mathcal{B},mu,T)$ be an ergodic measure preserving system, $A in mathcal{B}$ and $epsilon>0$. We study the largeness of sets of the form begin{equation*} begin{split} S = left{ ninmathbb{N}colonmu(Acap T^{-f_1(n)}Acap T^{-f_2(n)}Acapldotscap
T^{-f_k(n)}A)> mu(A)^{k+1} - epsilon right} end{split} end{equation*} for various families ${f_1,dots,f_k}$ of sequences $f_icolon mathbb{N} to mathbb{N}$. For $k leq 3$ and $f_{i}(n)=i f(n)$, we show that $S$ has positive density if $f(n)=q(p_n)$ where $q in mathbb{Z}[x]$ satisfies $q(1)$ or $q(-1) =0$ and $p_n$ denotes the $n$-th prime; or when $f$ is a certain Hardy field sequence. If $T^q$ is ergodic for some $q in mathbb{N}$, then for all $r in mathbb{Z}$, $S$ is syndetic if $f(n) = qn + r$. For $f_{i}(n)=a_{i}n$, where $a_{i}$ are distinct integers, we show that $S$ can be empty for $kgeq 4$, and for $k = 3$ we found an interesting relation between the largeness of $S$ and the abundance of solutions to certain linear equations in sparse sets of integers. We also provide some partial results when the $f_{i}$ are distinct polynomials.
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be st
ored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r<=m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves done by the algorithm. This problem is non-trivial when n=<m<r. In the case that m=Cn for some C>1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Omega(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
The $alpha$-fair resource allocation problem has received remarkable attention and has been studied in numerous application fields. Several algorithms have been proposed in the context of $alpha$-fair resource sharing to distributively compute its va
lue. However, little work has been done on its structural properties. In this work, we present a lower bound for the optimal solution of the weighted $alpha$-fair resource allocation problem and compare it with existing propositions in the literature. Our derivations rely on a localization property verified by optimization problems with separable objective that permit one to better exploit their local structures. We give a local version of the well-known midpoint domination axiom used to axiomatically build the Nash Bargaining Solution (or proportionally fair resource allocation problem). Moreover, we show how our lower bound can improve the performances of a distributed algorithm based on the Alternating Directions Method of Multipliers (ADMM). The evaluation of the algorithm shows that our lower bound can considerably reduce its convergence time up to two orders of magnitude compared to when the bound is not used at all or is simply looser.
Let $X_1,X_2,ldots$ and $Y_1,Y_2,ldots$ be two random sequences so that every random variable takes values in a finite set $mathbb{A}$. We consider a global similarity score $L_n:=L(X_1,ldots,X_n;Y_1,ldots,Y_n)$ that measures the homology (relatednes
s) of words $(X_1,ldots,X_n)$ and $(Y_1,ldots,Y_n)$. A typical example of such score is the length of the longest common subsequence. We study the order of central absolute moment $E|L_n-EL_n|^r$ in the case where two-dimensional process $(X_1,Y_1),(X_2,Y_2),ldots$ is a Markov chain on $mathbb{A}times mathbb{A}$. This is a very general model involving independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a general condition that guarantees that $E|L_n-EL_n|^rasymp n^{rover 2}$. We also perform simulations indicating the validity of the condition.
The point placement problem is to determine the positions of a set of $n$ distinct points, P = {p1, p2, p3, ..., pn}, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distan
ce query corresponds to an edge in a graph, called point placement graph ppg, whose vertex set is P. The uniqueness requirement of the placement translates to line rigidity of the ppg. In this paper we show how to construct in 2 rounds a line rigid point placement graph of size 9n/7 + O(1). This improves the existing best result of 4n/3 + O(1). We also improve the lower bound on 2-round algorithms from 17n/16 to 9n/8.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
