3. Complexity Theory

Stephen J. WrightSociety 1997 · DOI · OpenAlex

Abstract

In this chapter, we discuss a purely theoretical issue: basic complexity theory for linear programming. We ask such questions as, Can we find an upper bound on the time needed by an algorithm to solve a given instance of a linear programming problem? Can we estimate the time required to solve a “typical” problem instance? What properties of the problem instance does the bound depend on, and how does it depend on them?
BibTeX
@inproceedings{wright1997complexity,
  author = {Stephen J. Wright},
  title = {{3. Complexity Theory}},
  booktitle = {Society},
  year = {1997},
  doi = {10.1137/1.9781611971453.ch3},
}

Loading related content...

Figure