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

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.