0
$\begingroup$

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?

$\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.hatam
    Jun 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.hatam
    Jun 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$
    – domotorp
    Jun 24 at 7:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.