• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A combinatorial algorithm for Horn programs
【24h】

A combinatorial algorithm for Horn programs

机译：Horn程序的组合算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we design and analyze a simple, greedy algorithm for checking the linear and integer feasibility of a class of linear programs called Horn programs. This algorithm, which we term the "Lifting Algorithm", runs in time O(m□~(n2)) on a Horn system (Horn program) with m constraints and n variables. The Lifting Algorithm is a variant of the Stressing Algorithm which was proposed for checking the feasibility of Difference Constraint systems. Inasmuch as Horn constraints subsume difference constraints, and all known algorithms for the problem of checking feasibility of Difference Constraint Systems run in time Ω(m□n), the running time of our algorithm is only a factor n worse than the best known running time for checking the feasibility of Difference Constraint Systems. Horn programs arise in a number of application areas including econometrics and program verification; consequently, their study is well-motivated. An important feature of our algorithm is that it uses only one operator, viz., addition. We also show that our algorithm can identify the linear and lattice point feasibility of Extended Horn Systems in O(m□~(n2)) time.
机译：在本文中，我们设计并分析了一种简单的贪婪算法，用于检查称为Horn程序的一类线性程序的线性和整数可行性。该算法（我们称为“提升算法”）在具有m个约束和n个变量的Horn系统（Horn程序）上以O（m□〜（n2））的时间运行。提升算法是应力算法的一种变体，提出该算法是为了检查差异约束系统的可行性。由于Horn约束包含差异约束，并且所有用于检查差分约束系统可行性的已知算法都在时间Ω（m□n）中运行，因此我们的算法的运行时间仅比已知的最佳运行时间差n个因子用于检查差异约束系统的可行性。 Horn程序出现在许多应用领域，包括计量经济学和程序验证;因此，他们的学习动机良好。我们算法的一个重要特征是它仅使用一个运算符，即加法。我们还表明，我们的算法可以确定O（m□〜（n2））时间内扩展Horn系统的线性和晶格点可行性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号