Edit · 2026 07 10 102523 Deepbluelibumichedu Full

Saving needs a token. Log in or register to get one. Edits are public and licensed CC-BY-SA-4.0.

# 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)

Cancel

Preview · live