インターバル保存要求を処理するスタック

An interval storage request is represented by a tuple $(s,t,v)$
satisfying $s

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

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

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

(ii) (capacity constraint) for any $tin [T]$, there is no
integer $kin [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 iin [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.

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です