The game is defined by two integer parameters: n and k. We are given an array of n sets: $$S_1, S_2, ...., S_n$$ such that, each of them is a subset of $\{1, 2, ..., k\}$. Adversary picks a set $S_i$ in each turn and changes it into an empty set. the cost that we must paid is a minimal number $t$ such that: $$S_i \subseteq S_{i-t} \cup S_{i-t+2} \cup ... \cup S_{i-1}$$ or $$S_i \subseteq S_{i+1} \cup S_{i+2} \cup ... \cup S_{i+t}$$ if there is no such $t$ we must pay: $$min(i, n-i)$$ can we settle an upper bound on the amortized cost of $n-1$ turns?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Do you want a bound that holds for all possible arrays, and depends on only $n$ and $k$? What regime of $k,n$ are you interested in? Where $k$ is very small compared to $n$? Where $k$ is comparable to $n$? If there is no $t$ such that either equation holds, then am I correct to assume that the cost is $+\infty$? What's the motivation for this question or the context where it arises? What have you tried? What is the best bound you have been able to find so far? $\endgroup$– D.W.Jun 22 at 20:07
-
$\begingroup$ when there is not such $t$, we must paid $min(i, n-i)$. I interest in cases that $k = o(log n)$. $\endgroup$– R.hatamJun 23 at 7:35
-
$\begingroup$ I'm motivated to this problem because it is very helpfull tool for online algorithm analysis. I fact I want to solve this problem to settle an upper bound on competitive ratio on an online algorithm for chordal graphs coloring. $\endgroup$– R.hatamJun 23 at 7:42
-
1$\begingroup$ Your question does not match your comment. $\min(i,n-i)$ or $\min(n,n-i)$? Please edit the question accordingly. $\endgroup$– D.W.Jun 23 at 17:22
-
$\begingroup$ The quantifiers are not clear at all. An adversary gives the array of sets, and also the adversary picks the $i$ in each round, i.e., we have no choice anywhere in this game? $\endgroup$– domotorpJun 24 at 7:31
Add a comment
|