Provably efficient algorithms for resolving temporal and spatial difference constraint violations
Provably efficient algorithms for resolving temporal and spatial difference constraint violations
复制标题
用于解决时间和空间差异约束违规的可证明有效的算法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Ali Dasdan
中科院分区：
文献类型：
--
作者：
Ali Dasdan
差异约束系统是调度、约束满足和布局压缩等许多领域的时间和空间约束的形式模型。在这样的系统构建过程中，经常会出现约束违规的情况，需要解决。以前用于此任务的算法分为两类：那些速度快但无法解决所有违规的算法，以及那些可以解决所有违规但速度呈指数级缓慢的算法。我们提出了第一个快速且能够解决所有违规问题的算法。此外，与以前的算法不同，我们的算法支持使用其固有的关键性或用户定义的优先级对违规进行排序。我们通过实验证明了我们算法的效率和功效。
A system of difference constraints is a formal model of temporal and spatial constraints in many areas such as scheduling, constraint satisfaction, and layout compaction. During construction of such a system, constraint violations often arise, and they need to be resolved. Previous algorithms for this task fall into two groups: those algorithms that are fast but cannot resolve all violations, and those algorithms that can resolve all violations but are exponentially slow. We propose the first algorithms that are fast as well as able to resolve all violations. Moreover, unlike the previous algorithms, our algorithms support the ordering of violations using their inherent criticality or user-defined priority. We provably and experimentally justify the efficiency and efficacy of our algorithms.