这个问题大思路是一样的 —— 启发式求解加一些 bounding 的技术。不同的是，图着色问题并不要求子集合，由于要对整张图进行着色，所以没有「永远扔掉」这个概念，每个点最后都要返回去，这个点一定要有一个颜色。这里的 reduce 是把图分解为 Kernel 和 Margin：
有一个很简单的规则，还是与独立集有关，我如果知道这个图至少需要用多少种颜色，就是颜色下界（记为ℓ），则可以找到ℓ-degree bound 的独立集。这个独立集的点的度数都比ℓ小，所以叫做ℓ-degree bound。如果找到这样的独立集，可以放心移到 Margin 里面。如果把 kernel 的 solution 找出来之后，我们可以很方便把 Margin 合并进来，如果 kernel 是最优解，合起来一定也是最优解，这个规则可以迭代地去使用。
我们看一个例子，这个例子里面灰色的四个点是 kernel，可以看到至少需要 4 种颜色。旁边的三个点放到边缘上，因为三个点的度数都比 4 小，我们放心把这三个点挪到旁边先不管。然后发现剩下这个子图分解不动，已经很硬核了，可以直接求解出来。稀疏图的硬核一般都不大，所以可以考虑精确算法求解。如果把核心找出来，因为已知核心至少用四个颜色，对于边缘中的点，每个点的度数小于 4，怎么样都留有一个颜色给它，走一遍就可以了，线性的时间就可以了。
直到最后，每一次剥离的 Margin 都要保留下来，而且要标记清楚是第几层，这是与第一个问题稍微不同的地方。我们要用额外数据结构把这些边缘图保留下来，最后一个剥不动的 Kernel 精确化解决之后，就可以用倒序的方法，先把最后一个 Margin 给合并进来，根据刚才的规则保留最优性，Kernel 是最优的话，合并一个边缘还会是最优，一路回溯上去，那原图的解也一定是最优的。
当这个问题变成有框架的之后，就只剩下考虑如何找 lower bound 和 upper bound。算法的大致思路是：一开始 kernel 是原图，需要用到最大团算法找一个 lower bound；剥掉边缘之后，可以采取贪心图着色算法，找一个 upper bound。
这里其实用到了三种算法。实践中比较常见组合拳打法，具体到做 kernel 着色，当这个图比较大的时候，我们可能通过某种贪心或者比较快的方法去做，最后有可能变成精确算法去做。整个流程中，lower bound 和 upper bound 都是全局的，如果这两个相等，就可以停下了。
上图是实验结果，可以看出在稀疏大图上面的效果更好，144 个中里有 97 个可以在一分钟内证明最优解。跟同类算法相比，我们的算法对比时间也比较快，在比较稀疏大图上面有特殊方法可以很快求解。大家以前认为，几百万顶点的 NP 难问题肯定要算很久，其实，如果这些图很大但有一定特点的话，我们还是可以在秒级和分钟级的时间内解决的。
阿里妈妈 CTO 郑波：阿里妈妈持续升级的决策智能技术体系
大家好，作为阿里妈妈技术负责人，我将从业界视角分享一下过去几年阿里妈妈在决策智能技术上的进展。
阿里妈妈创立于 2007 年，是阿里巴巴集团的核心商业化部门，也就是在线广告部门。经过了十几年的发展，阿里妈妈打造过「搜索广告淘宝直通车」这样有影响力的产品，2009 年有了展示广告、Ad Exchange 广告交易平台，2014 年又出现了数据管理平台达摩盘，2016 年开始做全域营销。
从技术上看的话，在 2015 年、2016 年前后，阿里妈妈全面拥抱深度学习，从智能营销引擎 OCPX 到自研 CTR 预估核心算法 MLR 模型，都是随着深度学习的方法不断演进的。2018 年，深度学习框架 X-Deep Learning 开源。2019 年，Euler 图学习框架开源，信息流产品超级推荐也上线了，「人找货」进化到了「货找人」。2020 年开始，阿里妈妈针对直播类型的广告上线，同时开始推出互动激励广告，比如大家玩得比较多的互动游戏「双十一」叠猫猫。曲率空间学习框架也在这一年开源。
2022 年，阿里妈妈将整个广告引擎做了重大升级。广告引擎平台 EADS 和多媒体生产与理解平台 MDL 都上线了；在消费者隐私保护上，阿里妈妈的隐私计算技术能力获得了中国信通院认证。回顾阿里妈妈过去十五年的发展，可以看出，我们是一家「根正苗红」做计算广告的公司。
阿里妈妈有什么优势呢？在非常专业的电商场域，我们对用户和电商理解是非常强的，业务场景也非常丰富，除了传统的搜索推荐是传统，在直播推广、互动、新形态等数智业务场景上都有涉猎。此外我们的客户规模属于全球领先，几百万的商家都是阿里妈妈平台的广告客户。这些客户有非常多的需求，除了商家对经营的需求，还有各种各样的生态角色涉及其中，比如主播、达人或者代理商、服务商，他们以不同角色在这个平台里活跃。
我们在 AI 方面也有比较多的研究。这里介绍一下广告场景算法技术的特色。如上图，左边的倒漏斗型结构，很多做搜索或者推荐同学非常熟悉，这一部分广告和搜索推荐非常相似，包括广告召回、粗排序、精排序到机制策略的打分，涉及到信息检索等大量 AI 技术，特别是匹配上的 TDM 等召回模型都用了深度学习的技术。
其中包括决策智能，鉴于平台包含非常多的角色，各有各的博弈的关系，在多方关系和优化平衡之间，决策智能就派上了用场。用户体验、流量成本、预期收益、预算控制、跨域的融合，这些都是需要去博弈平衡的。
