eldorado.tu-dortmund.de/server/api/core/bitstreams/35dd3ec1-8ebf-443f-b970-76fbf17dc2e7/content
Bulk-Robust Assignment Problems: Hardness, Approximability and Algorithms
= (x, r, c2S, c3S,p1,p2, . . . ,p2d, x),
where P := (p1,p2, . . . ,p2d), d ∈ Z+. In the first subcase we assume S 6∈ V(P). Then the M-cycle
D = (x, r,S, c1S, c2S, c3S,p1,p2, . . . ,p2d, x)
can be used [...] x, c3S, c2S,p1,p2, . . . ,p2d, r),
where P := (p1,p2, . . . ,p2d), d ∈ Z+, be an M-cycle in G+ L. In case S ∈ V(P), i.e., the cycle C can be written as
C = (r, x, c3S, c2S,p1,p2, . . . ,p2d ′ , c1S,S,q1 [...] scenarios.
3.7 constant-factor approximation for card-e-rap 61
5
3
1
6
4
2
5
3
1
6
4
2 P0
P1
P2P2
5
3
1
6
4
2 P0
P1
P2P2
Figure 11: Illustration of Algorithm 4. From left to right: Input graph, its ear d …