The image of weighted combinatorial problems (Q1179736)

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.