### 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(n^{2}) where n is the number of constraints in C, while computing the solved form directly has expected cost O(n^{3}). To our knowledge this is the first incremental algorithm for (re)computing a solved form after deleting a constraint.

Original language | English |
---|---|

Pages (from-to) | 111-115 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 55 |

Issue number | 2 |

DOIs | |

Publication status | Published - 21 Jul 1995 |

Externally published | Yes |

### Keywords

- Algorithms
- Incremental
- Linear arithmetic constraints

### Cite this

}

*Information Processing Letters*, vol. 55, no. 2, pp. 111-115. https://doi.org/10.1016/0020-0190(95)00063-I

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

Research output: Contribution to journal › Article › Research › peer-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 -