pocketz.doi.bio/2026-07-10_102523_deepbluelibumichedu_full

The Complexity of Some Problems in Parametric Linear and Combinatorial Programming.

URL: https://deepblue.lib.umich.edu/items/74bbfd9a-e53b-4941-ad3b-06ae211172c5/full

Saved: 2026-07-10T17:25:23.749Z

Home Research Collections Dissertations and Theses (Ph.D. and Master's) The Complexity of Some Problems in Parametric Linear and Combinatorial Programming. The Complexity of Some Problems in Parametric Linear and Combinatorial Programming. Simple work page dc.contributor.affiliationumcampus Ann Arbor

dc.contributor.author Carstensen, Patricia June

dc.date.accessioned 2020-09-09T00:48:29Z

dc.date.available 2020-09-09T00:48:29Z

dc.date.issued 1983

dc.description.abstract In this dissertation, linear and combinatorial problems in which the cost is a linear function of a parameter (lamda) are considered. The complexity of such problems can be measured by the number of slope changes in the optimal cost curve. It is shown that: (1) In linear programming, the number of slope changes is, in the worst case, exponential in the number of variables, regardless of the size of the data. However, in 0-1 programming, the number of breakpoints is polynomial in n and in the maximum absolute data element. (2) In the parametric cost minimum cost flow, the parametric capacity maximum flow, and the parametric cost minimum cut problems, the number of slope changes is exponential in the number of nodes in the network in the worst case. However, the number of slope changes is polynomial in n and in the maximum data element. (3) In the parametric cost knapsack problem and many other Np-complete 0-1 problems, the number of slope changes may be as large as 2('SQRT.(n(' ))-(' )1, where n is the number of variables. However, the number of slope changes is polynomial in n and in the maximum data element. (4) Finally, in the parametric cost shortest chain problem, the number of slope changes may be n('Dlog n), where D is a positive number and n is the number of nodes. Again, the number of breakpoints is polynomial in n and in the maximum data element. It is also shown that the intermediate feasibility problem is NP-complete.

dc.description.bitstreamurl http://deepblue.lib.umich.edu/bitstream/2027.42/159350/1/8314249.pdf en_US

dc.description.thesisdegreediscipline Mathematics

dc.description.thesisdegreegrantor University of Michigan

dc.description.thesisdegreename PhD en_US

dc.format.extent 206 p.

dc.identifier.uri https://hdl.handle.net/2027.42/159350

dc.language English

dc.subject.hlbtoplevel Science

dc.title The Complexity of Some Problems in Parametric Linear and Combinatorial Programming.

dc.type Thesis
Files Original bundle Now showing 1 - 1 of 1 Name: 8314249.pdf Size: 5.65 MB Format: Adobe Portable Document Format Description: Restricted to UM users only. Download Collections Dissertations and Theses (Ph.D. and Master's)