Before revision:  We consider two optimization goals: either minimizing the number of line segments or minimizing the number of bend points in the simplification. By reduction from Minimum-Independent-Dominating-Set, we show that both of these optimization problems are NP-hard to approximate within a factor n^{1/3 - \varepsilon} for any \varepsilon > 0 where n is the number of bend points in the polyline bundle.
After revision:  We consider two optimization goals: either minimizing the number of line segments or minimizing the number of bend points in the simplified bundle with respect to some error tolerance \delta (measuring Fr\'echet distance) but under the additional constraint that shared parts have to be simplified consistently. We show that polyline bundle simplification is NP-hard to approximate within a factor n^{1/3 - \varepsilon} for any \varepsilon > 0 where n is the number of bend points in the polyline bundle.