Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation

Jonas Friemel, Tilo Hoitz, Phillip Keldenich +1

We consider a matching problem in which the cost of each edge is a vector with $k$ components. The cost of a matching is the sum of the bottlenecks over all components, and we ask…