Back to search

West Virginia University

Properties of chain programs over difference constraints

Abstract

dc:description.abstract

Chain Programming is a restricted form of linear programming in which there exists a total ordering over the program variables. In other words, the constraints x1 ≤ x 2 ≤ ... ≤ xn are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary Chain Program is easier to solve than a linear program, either asymptotically or computationally. This thesis presents a variety of interesting properties pertaining to the case in which a Chain Program is constituted entirely of difference constraints. Deciding the feasibility of a system of difference constraints is a well-studied problem. When a system of difference constraints includes the constraints x 1 ≤ x2 ≤ ... ≤ xn, it is an instance of Chain Programming over Difference Constraints. Existing methods for deciding the feasibility of systems of difference constraints may be used for Chain Programs over Difference Constraints, but the properties of this problem strongly suggest that a more efficient method may exist.

Degree

thesis:*
Name thesis:degree_name
MS
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Argentieri, John E.

Subjects

dc:subject × 1

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Argentieri, John E.. Properties of chain programs over difference constraints. Thesis thesis, https://doi.org/10.33915/etd.2297