M39
自习室座位与考场的在线分配：受限区间图在线染色的竞争比上下界
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
把"自习室座位/考场随到随分、不可中途换座"建模为区间图在线染色（online interval graph coloring）：当请求区间满足现实约束——长度只取 k 种离散值（如 1/2/3 节课）——时，最优在线算法的竞争比（competitive ratio）是多少？能否给出上界（算法 + 证明）与下界（对手论证）并使二者收紧？
2 · 研究背景与空白
在线区间染色是在线算法的经典问题：区间逐个到达，须立即着色（= 分配座位/教室），同色区间不得相交，目标是少用颜色。Kierstead–Trotter（1981）给出 3ω − 2 色的在线算法并证明其最优（ω 为团数，即峰值并发数）——一般情形竞争比 3 已定。但受限输入类改变答案：单位区间情形竞争比降到 2（已有文献），长度受限、到达顺序受限等变体各有部分结果与空档（需核实：搜索关键词 online interval coloring bounded lengths competitive ratio Epstein）。竞争比证明是纯组合数学：上界是算法不变量归纳，下界是显式对手策略构造——两个方向都是严格定理。
已有工作：Kierstead–Trotter 定理；单位区间与若干变体的竞争比（第 3 周核实到"k 种长度"情形的现状——该情形有文献但上下界未必匹配）。丘奖相邻获奖论文：2025 入围《Mathematical modeling for physician scheduling in fever clinics based on dynamic mixed integer programming》（排班建模，离线 MIP）——本题差异：在线模型 + 竞争比定理（最坏情形保证 vs 单实例优化）。
空白在：k 种离散长度（现实课表约束的最简抽象）下竞争比作为 k 与长度比的函数，已知上下界之间存在可攻的缝隙（第 3 周核实精确缝隙；若该缝已闭合则转嵌套长度/层级到达等次级变体，框架不变）。适合学生：问题陈述贴近生活（答辩友好）、证明工具是初等组合与归纳、模拟验证便宜。
3 · 可检验假设
- H1：k = 2、长度比为整数 r 时，存在在线算法用 ≤ c(r)·ω + O(1) 色（c(r) < 3 显式），且有对手构造迫使 ≥ c'(r)·ω 色,c 与 c' 的差距 ≤ 0.5。
- H2：真实课表型输入（半随机到达）下，该算法的实测用色 / 峰值并发比值显著低于最坏情形保证（定量：均值 + 95% CI），即最坏情形界在现实分布下保守。
4 · 量化验收标准
- 方法学校验（硬门槛）：仿真框架先复现两个已知定理的数值表现——(a) Kierstead–Trotter 算法实现，在其理论下界对手实例上实测触及 3ω − 2 色;(b) First-Fit 在区间图上的已知非常数竞争比劣化行为定性复现（随对手实例规模增长）。不过关则实现有误，全线无效。
- 定理交付：k = 2 情形的上界算法 + 完整证明，与下界对手构造 + 完整证明；明确报告缝隙宽度。
- 数值交付：上界算法在 ≥ 10⁵ 随机与对抗实例上机器验证不变量零违例（不变量违例即证明有洞，回炉）。
- 应用检验：以一份真实学校课表节奏生成半随机请求流（自己学校的公开作息表，无隐私数据），报告 H2 的定量结论；明确标注该部分为实证补充，不计入定理。
- 统计口径：随机实例报均值 ± 95% CI（分布自助法）；对抗实例逐例列表。
- 代码开源，一键复跑（全套 < 2 小时）。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 仿真框架 | 自写 Python（区间流生成、在线算法接口、不变量检查器） |
| 经典算法对照 | Kierstead–Trotter 与 First-Fit 自实现（仅校验与基线，不计入贡献） |
| 文献 | 在线染色综述与变体论文（arXiv 免费；第 3 周核实 k-长度情形现状） |
| 课表节奏 | 本校公开作息时间表（自采，无个人数据） |
| 算力量级 | 全部模拟笔记本分钟级，纯 CPU；本题计算最轻档 |
6 · 方法路径
- 搭仿真框架 + 实现 KT/First-Fit，完成第 4 块第 1 条复现。
- 文献窗口：核实 k 种长度情形的最好上下界（能力边界核实步），锁定缝隙目标。
- 设计 k = 2 算法（按长度分层 + 层内单位区间技术的杂交是首选路线），先模拟摸行为再证上界。
- 构造下界对手（在长区间上"钓"算法浪费颜色的经典手法），证下界。
- 迭代收紧两端；每个版本的证明先过不变量机器验证再手工成文。
- 跑课表型实证补充；成文时写清定理/实证边界。
7 · 新颖性边界
- 本课题不声称改进一般区间在线染色的竞争比 3（Kierstead–Trotter 已定），不把单位区间等已解变体计入贡献。
- 已有工作：KT 定理；单位区间竞争比；长度受限变体的部分界（第 3 周核实到定理级，已发表的界作为本题的比较基线，不计入贡献）。丘奖相邻获奖论文：2025 入围《Mathematical modeling for physician scheduling in fever clinics based on dynamic mixed integer programming》——本题差异：在线对最坏情形的定理保证 vs 离线单实例优化；模型对象（教室/座位分配）与方法（竞争分析）均不同。
- 本项目贡献（主结论）：k 种长度变体的新上界或新下界（任一端改进即成立），目标是缝隙收紧 + 现实分布下的保守度量化。
- 价值：竞争比定理是永久性组合结果;"最坏情形理论 vs 现实分布表现"的对照回答了应用者真正关心的问题，负结论（缝隙收不动但保守度量化完成）仍自足。
8 · 决策门槛（go / no-go）
- 第 3 周末：现状核实完成。若 k = 2 缝隙已闭合 → 顺位转嵌套长度族/带取消请求/层级到达变体（预排序清单），框架与仿真器复用。
- 第 6 周末：硬门槛复现通过。
- 第 16 周末：若上下界两端均无改进,降级路径 A：把已知上界算法的加性常数项收紧（O(1) 项的精确化也是干净结果）+ H2 实证;降级路径 B：转"随机到达顺序"模型（competitive ratio 换成期望用色比，分析工具变概率但框架保留）。
- 第 30 周末：冻结定理陈述，转撰写；实证章节可并行。
- 预算裁剪顺序：H2 实证 → 第二个变体探索；主定理（至少一端的新界）不砍。