The image of weighted combinatorial problems (Q1179736)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The image of weighted combinatorial problems |
scientific article |
Statements
The image of weighted combinatorial problems (English)
0 references
27 June 1992
0 references
The concept of image of an integrally weighted combinatorial problem is introduced as the vector of all possible weights of feasible solutions. This preliminary work begins to explore the possible applications of this concept and to study the computational complexity of image computations. It is shown that the images of matroid parity bases can be computed in polynomial time for some ``bottleneck'' objective functions, whereas (random) pseudo-polynomial time is needed when the objective function is the sum of the element weights.
0 references
image of weighted combinatorial problems
0 references
matroid parity bases
0 references