Predicate Detection to Solve Combinatorial Optimization Problems
Predicate Detection to Solve Combinatorial Optimization Problems
复制标题
谓词检测解决组合优化问题
DOI：
10.1145/3350755.3400235
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Garg, Vijay K.
中科院分区：
文献类型：
--
作者：
Garg, Vijay K.
我们提出了一种为约束组合优化问题设计并行算法的方法。我们的方法解决并推广了许多经典的组合优化问题，包括稳定婚姻问题、最短路径问题和市场出清价格问题。文献中使用Gale-Shapley算法、Dijkstra算法以及Demange、Gale、Sotomayor算法来解决这三个问题。我们的方法通过将它们视为在分配格中搜索满足适当谓词的元素来解决所有这些问题。此外，它解决了所有这些问题的概括——即找到满足称为格线性谓词的附加约束的最佳解决方案。对于稳定的婚姻问题，这种约束的一个例子是彼得的遗憾比保罗的遗憾少。对于最短路径问题，此类约束的一个示例是到达顶点 v1 的成本至少是到达顶点 v2 的成本。对于市场出清价格问题，此类约束的一个示例是 item1 的定价至少与 item2 一样多。我们的算法称为格线性谓词检测 (LLP)，可以并行实现，无需任何锁或比较和设置指令。它只是假设读取和写入的原子性。
We present a method to design parallel algorithms for constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem. These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra's algorithm, and Demange, Gale, Sotomayor algorithm. Our method solves all these problems by casting them as searching for an element that satisfies an appropriate predicate in a distributive lattice. Moreover, it solves generalizations of all these problems --- namely finding the optimal solution satisfying additional constraints called lattice-linear predicates. For stable marriage problems, an example of such a constraint is that Peter's regret is less than that of Paul. For shortest path problems, an example of such a constraint is that cost of reaching vertex v1is at least the cost of reaching vertex v2. For the market clearing price problem, an example of such a constraint is that item1is priced at least as much as item2. Our algorithm, called Lattice-Linear Predicate Detection (LLP) can be implemented in parallel without any locks or compare-and-set instructions. It just assumes atomicity of reads and writes.
数学晶体学中的晶格问题
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
折田 充;小林 景;村里 泰昭;吉井 誠;Richard Lavin;相澤 一美;Ryoko Oishi-Tomiyasu;富安 (大石) 亮子
通讯作者：
富安 (大石) 亮子
影响因子：
1.1
作者：
Vânia M. F. Dias;G. D. D. Fonseca;C. M. Figueiredo;J. Szwarcfiter
通讯作者：
J. Szwarcfiter