3
$\begingroup$

An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in the following natural way: at time $s$, it push an entry with content $v$ into the stack, and pop it out at time $t$. Note that a stack can only pop out its top entry. This implies that a single stack cannot serve two requests $(s_1,t_1,v_1)$, $(s_2,t_2,v_2)$ where $s_1<s_2<t_1<t_2$, since at time $t_1$, the top entry of the stack is $v_2$ rather than $v_1$. However, with two stacks we can serve both requests easily.

The question is: given a set of interval storage requests and capacitated machines, what is the largest subset (in cardinality) of the requests such that we can find a way to serve them using the given stacks (when a request come, we can decide which stack to push it in)?

The formal statement of the problem is the following. We say two intervals $[s_i,t_i]$ and $[s_j,t_j]$ cross if $s_1<s_2<t_1<t_2$ or $s_2<s_1<t_2<t_1$.

Given intervals $I=\{[s_i,t_i]\}_{i\in [n]}$ (assume all endpoints are different integers in $[2n]$), together with integer $T$ and $\{m_t\}_{t\in [T]}$, find a collection of disjoint subsets $J_1,\cdots, J_T\subseteq [n]$ with the largest sum of cardinalities $|J_1|+\cdots+|J_T|$ such that:

(i) (no crossing) for any $t\in [T]$, no two intervals in $I_{J_t}=\{[s_i,t_i]\mid i\in J_t\}$ cross;

(ii) (capacity constraint) for any $t\in [T]$, there is no integer $k\in [2n]$ such that $k$ is contained in at least $m_t+1$ intervals in $I_{J_t}$.

The case $T=1$ is easy. Some other interesting special cases include:

(a) $\forall i\in [T], m_i=\infty.$ Namely, there is no capacity constraint.

(b) Determine whether or not all requests can be served.

I wonder if this problem (or any of the above special cases) was studied before? Any previous results or new ideas are appreciated.

$\endgroup$
  • $\begingroup$ Keywords: coloring, interval graph, online algorithm? $\endgroup$ – François G. Dorais Dec 1 '17 at 22:44
  • $\begingroup$ @François G. Dorais I thought about this. But the problem does not ask for online algorithms (it can, but that's an variant). On the other hand, it is not an "interval graph" problem, since we allow intervals to overlap, but only not cross. However, it does not hurt to add them, thanks. $\endgroup$ – Zihan Tan Dec 1 '17 at 23:42

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.