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

@article{c3b958a29b8b4265a949667899fbedff,
title = "Incremental constraint deletion in systems of linear constraints",
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.",
keywords = "Algorithms, Incremental, Linear arithmetic constraints",
author = "Tien Huynh and Kim Marriott",
year = "1995",
month = "7",
day = "21",
doi = "10.1016/0020-0190(95)00063-I",
language = "English",
volume = "55",
pages = "111--115",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "2",

}

Incremental constraint deletion in systems of linear constraints. / Huynh, Tien; Marriott, Kim.

In: Information Processing Letters, Vol. 55, No. 2, 21.07.1995, p. 111-115.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Incremental constraint deletion in systems of linear constraints

AU - Huynh, Tien

AU - Marriott, Kim

PY - 1995/7/21

Y1 - 1995/7/21

N2 - 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.

AB - 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.

KW - Algorithms

KW - Incremental

KW - Linear arithmetic constraints

UR - http://www.scopus.com/inward/record.url?scp=0011746774&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(95)00063-I

DO - 10.1016/0020-0190(95)00063-I

M3 - Article

VL - 55

SP - 111

EP - 115

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -