本文提供了一种面向带权有向图的广义框架，可以计算（估算）多次边权重，并以不同准确性和运行时开销进行优化，从而提出了一个最短路径问题的广义形式。我们介绍了该问题的一个完整的任何时刻的解法算法，并在实验中证明了其有效性。

Aug, 2022

研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变，并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。

Mar, 2008

本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

Nov, 2014

本研究分析了现有图嵌入神经网络（GNN）在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性；通过研究聚集 - 合并 GNN（AC-GNN）的性能以及其基于局部搜索的特性，我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则，并提出了一个简单的 AC-GNN 变体以验证我们的理论，并实现了比现有启发式算法更高质量和更快速运行的结果。

Aug, 2022

本文介绍了一种解决分簇问题的算法，在不允许颜色过于集中的情况下进行经典分簇，使用线性规划方法得到分数解并进行四舍五入，同时提供了特殊情况下经过简化的组合算法。实验表明该算法能够有效地解决分簇问题，避免了过度集中。

May, 2019

通过改进 BPP 启发式算法以及提出新的 CBPP 启发式算法，并结合基于变量邻域搜索 (VNS) 和数学启发式方法的邻域搜索算法，我们的研究表明，我们的数学启发式方法优于 VNS，两种方法都可以在大量实例中找到近乎最优的解，甚至对于具有许多物品的实例也是如此。

Oct, 2023

本文介绍了一个新的随机算法 — 边行走算法，用于寻找松散套的一个例子，这个算法的分析仅仅使用基本的线性代数，是一个新定理的证明，证明了 Spencer 定理和部分着色引理。

Mar, 2012

给定一个系统 (V,S)，其中 V={1,...,n}，S={S1,...,Sm}，最小偏差问题是要找到一个 V 的二分图着色，使得每个集合的着色尽可能均匀。本文提出了首个多项式时间算法来最小化偏差，并使用所谓的熵方法获得可实现的界限。我们还对偏差进行了首次近似结果，算法的主要思想是通过让元素的颜色随机行走（带有微小的增量）从 0 开始，直到它们达到 - 1 或 + 1，以随时间产生一个着色方案。在每个时间步骤中，使用解决当前状态和熵方法所确定的半定规划的解来获取多个元素的随机跳跃相关性。

Feb, 2010

在加权有向图中解决最短路径问题时，考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上，引入了找到最紧适应最短路径（TASP）的问题，该路径在最优成本的上界上最紧缩，实现了对有界不确定性的最短路径问题的泛化，其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP，并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。

Aug, 2023

研究了在线最短路径问题及其各种监控模型，在加权有向无环图中寻找一条路径以使其对应的边权和尽可能小。提出了一种算法，将累积损失最小化，并介绍了其应用于包交换网络中路由的模拟结果。

Apr, 2007