Incremental constraint deletion in systems of linear constraints

Tien Huynh, Kim Marriott

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

Suppose we are given a (possibly redundant) system of linear equalities and linear inequalities, C, and a solved form for C, and we now delete a constraint from C. We give an algorithm to incrementally compute a solved form for this new system. The algorithm has cost O(n2) where n is the number of constraints in C, while computing the solved form directly has expected cost O(n3). To our knowledge this is the first incremental algorithm for (re)computing a solved form after deleting a constraint.

Original languageEnglish
Pages (from-to)111-115
Number of pages5
JournalInformation Processing Letters
Volume55
Issue number2
DOIs
Publication statusPublished - 21 Jul 1995
Externally publishedYes

Keywords

  • Algorithms
  • Incremental
  • Linear arithmetic constraints

Cite this