Pseudo-polynomial time algorithms for combinatorial food mixture packing problems
Pseudo-polynomial time algorithms for combinatorial food mixture packing problems
复制标题
组合食品混合物包装问题的伪多项式时间算法
DOI：
10.3934/jimo.2016.12.1057
复制
发表时间：
2015
影响因子：
1.3
通讯作者：
Kenju Tateishi
中科院分区：
文献类型：
--
作者：
S. Imahori;Y. Karuno;Kenju Tateishi
A union $\mathcal{I}=\mathcal{I}_{1}\cup
\mathcal{I}_{2}\cup \cdots
\cup \mathcal{I}_{m}$ of $m$ sets of
items is given,
where for each $i=1,2,\ldots,m$,
$\mathcal{I}_{i}=\{I_{ik} \mid k=1,2,\ldots,n\}$
denotes a set of $n$ items of the $i$-th type
and $I_{ik}$ denotes the $k$-th item of
the $i$-th type. Each item $I_{ik}$
has an integral weight $w_{ik}$ and
an integral priority $p_{ik}$.
The food mixture packing problem
to be discussed in this paper
asks to find a union
$\mathcal{I}'=\mathcal{I}'_{1}\cup
\mathcal{I}'_{2}\cup \cdots
\cup \mathcal{I}'_{m}$ of $m$ subsets
of items so that for each
$i=1,2,\ldots,m$,
the sum weight of chosen items of
the $i$-th type for $\mathcal{I}'_{i}
\subseteq \mathcal{I}_{i}$
is no less than an integral indispensable
bound $b_{i}$, and
the total weight of
chosen items for $\mathcal{I}'$ is no less than
an integral target weight $t$. The total weight of
chosen items for $\mathcal{I'}$
is minimized as the primary objective,
and further
the total priority
of chosen items for $\mathcal{I'}$
is maximized
as the second objective.
In this paper, the known time complexity
$O(mnt+mt^{m})$ is improved to
$O(mnt+mt^{2})$ for an arbitrary $m\geq 3$
by a two-stage constitution algorithm with
dynamic programming procedures.
The improved time complexity figures
out the weak NP-hardness of the food mixture
packing problem.
A union $\mathcal{I}=\mathcal{I}_{1}\cup
\mathcal{I}_{2}\cup \cdots
\cup \mathcal{I}_{m}$ of $m$ sets of
items is given,
where for each $i=1,2,\ldots,m$,
$\mathcal{I}_{i}=\{I_{ik} \mid k=1,2,\ldots,n\}$
denotes a set of $n$ items of the $i$-th type
and $I_{ik}$ denotes the $k$-th item of
the $i$-th type. Each item $I_{ik}$
has an integral weight $w_{ik}$ and
an integral priority $p_{ik}$.
The food mixture packing problem
to be discussed in this paper
asks to find a union
$\mathcal{I}'=\mathcal{I}'_{1}\cup
\mathcal{I}'_{2}\cup \cdots
\cup \mathcal{I}'_{m}$ of $m$ subsets
of items so that for each
$i=1,2,\ldots,m$,
the sum weight of chosen items of
the $i$-th type for $\mathcal{I}'_{i}
\subseteq \mathcal{I}_{i}$
is no less than an integral indispensable
bound $b_{i}$, and
the total weight of
chosen items for $\mathcal{I}'$ is no less than
an integral target weight $t$. The total weight of
chosen items for $\mathcal{I'}$
is minimized as the primary objective,
and further
the total priority
of chosen items for $\mathcal{I'}$
is maximized
as the second objective.
In this paper, the known time complexity
$O(mnt+mt^{m})$ is improved to
$O(mnt+mt^{2})$ for an arbitrary $m\geq 3$
by a two-stage constitution algorithm with
dynamic programming procedures.
The improved time complexity figures
out the weak NP-hardness of the food mixture
packing problem.