在线向量装箱与超图着色的阐明:更简单的证明与新的联系
《Discrete Applied Mathematics》:Online vector bin packing and hypergraph coloring illuminated: Simpler proofs and new connections
【字体:
大
中
小
】
时间:2026年09月25日
来源:Discrete Applied Mathematics 1.1
编辑推荐:
# 从OHC到OVBP的简单归约、FirstFit竞争比的几乎紧上界,以及OHC下界的组合划分问题
## 摘要片段
**引言与主要结果**
{0,1} d维向量装箱问题(VBP)的箱子容量为B,定义如下。
**输入:** $\mathcal{I} = \{v_1, \
# 从OHC到OVBP的简单归约、FirstFit竞争比的几乎紧上界,以及OHC下界的组合划分问题
## 摘要片段
**引言与主要结果**
{0,1} d维向量装箱问题(VBP)的箱子容量为B,定义如下。
**输入:** $\mathcal{I} = \{v_1, \ldots, v_n\}$,其中 $v_i \in \{0,1\}^d$,$i = 1, \ldots, n$。一个箱子容量参数 $B \in \mathbb{Z}^+$。
**输出:** 将 $\mathcal{I}$ 划分到可行箱子中的一个划分方案。
**目标:** 最小化划分中箱子的数量。
子集 $X \subseteq \mathcal{I}$ 称为可行箱子,若 $\sum_{v \in X} v \leq \vec{B}$。本文中我们使用符号 $\vec{B}$ 表示全B向量 $(B, \ldots, B) \in \mathbb{R}^d$。设 $\text{OPT}(\mathcal{I})$ 表示可行装箱中 $\mathcal{I}$ 所需的最少箱子数。
---
## 通过在线超图的在线关联矩阵给出OVBP的下界
设 $H$ 为具有 $n$ 个顶点的在线 $k$-均匀超图。我们将 $H$ 与一个大小为 $(\binom{n}{k}) \times n$ 的在线关联矩阵 $I_H$ 相关联,如下定义。将行标记为所有 $\binom{n}{k}$ 条超边,将列按顶点在 $H$ 中到达的顺序标记为对应顶点。我们用 $v \in e$ 表示顶点 $v$ 属于超边 $e$。当在线顶点 $v$ 到达时,定义 $v$ 的在线列向量如下:
$$I_H(e, v) = \begin{cases} 0, & \text{若 } v \notin e, \\ 1, & \text{若 } v \in e \text{,但 } e \text{ 的所有顶点尚未全部到达}, \\ 0, & \text{若 } v \in e \text{,且 } v \text{ 是最后到达的顶点} \end{cases}$$
---
## FirstFit在OVBP上的几乎紧界
我们在此概述通过双重计数证明上界的思路,详细证明将在相应的小节中给出。设 $\mathcal{I} = \{v_1, \ldots, v_n\}$ 为一个OVBP实例,在线向量按此顺序到达。将每个 $v_i$ 视为列向量,我们将 $\mathcal{I}$ 视为一个 $\mathcal{I}_{d \times n}$ 矩阵。为了证明 $\text{FF}$ 的上界,我们用两种方式计算矩阵 $\mathcal{I}$ 中所有条目的总和,记为 $w(\mathcal{I})$。设 $p = p(\mathcal{I})$ 表示 $\mathcal{I}$ 中某一行中最大元素之和。按行计数,我们有 $w(\mathcal{I}) \leq d \cdot p$。另一方面,我们按……
---
## 一个多族划分问题
设 $C \subseteq \mathbb{N}$。设 $\mathcal{F}$ 为 $C$ 的子集族。我们允许 $\mathcal{F}$ 中存在多个相同的子集,即 $\mathcal{F}$ 本身是一个多重集。我们称 $\mathcal{F}$ 为 $C$ 上的多族。用 $|\mathcal{F}|$ 表示 $\mathcal{F}$ 的基数,我们用 $[a]$ 表示集合 $\{1, 2, \ldots, a\}$,$a \in \mathbb{N}$。例如,以下 $\mathcal{F}$ 是 $[3]$ 上基数为 $|\mathcal{F}| = 12$ 的多族:
$$\mathcal{F} = \{\{1\}, \{2\}, \{3\}, \{1\}, \{1,3\}, \{1,3\}, \{2,3\}, \{1,3\}, \{1,2,3\}, \{1,2,3\}, \{1,2,3\}, \{1,2,3\}\}$$
**定义1** 设 $C = \{c_1, \ldots, c_q\} \subseteq \mathbb{N}$。设 $\mathcal{F}$ 为 $C$ 上的多族。设 $p \in \mathbb{N}$。我们称 $\mathcal{F}$ 是 $(p, C)$-多样的,若存在一个……
---
## 在线均匀超树着色的下界
借助定理9,我们准备证明定理4。我们的证明策略如图2所示。
**定理4(重述)** 设 $\text{ALG}$ 为任何针对 $k$-均匀超树的在线着色算法。则存在一棵至多有 $km - 1$ 个顶点的 $k$-均匀在线超树,使得 $\text{ALG}$ 使用至少 $m$ 种颜色。
**定理4的证明** 对于超图 $H$,用 $V(H)$ 表示其顶点集。若 $H$ 是当前输入的某个子超图,用 $\text{col}(H)$ 表示 $\text{ALG}$ 在该输入中分配给 $H$ 的顶点的颜色集合。设 $T_m$ 表示在线超树……
---
## 利益冲突声明
作者声明,他们不存在已知的可能影响本论文所报告工作的竞争性经济利益或个人关系。
## 致谢
我们感谢LAGOS 2023和《离散应用数学》期刊的匿名审稿人,他们的意见使本论文得到了大幅改进。Y.L.感谢Ekin Ergen。会议版本中定理9的证明更为复杂,当前简化的证明受到了Ekin Ergen的启发和讨论。D.P.感谢加拿大自然科学与工程研究协会(NSERC)的支持。本研究的部分工作在Y.L.作为博士后与D.P.合作期间完成。
**Yaqiao Li | Denis Pankratov | Yu Zhu**