Facility location under matroid constraints: fixed-parameter algorithms and applications

06/29/2018
by   René van Bevern, et al.
0

We study an NP-hard uncapacitated discrete facility location problem: The task is to decide which facilities to open and which clients to serve for maximum profit so that the facilities form an independent set in given facility-side matroids and the clients form an independent set in given client-side matroids. Combining the color coding technique with representative sets of matroid intersections, we show that the problem is fixed-parameter tractable parameterized by the number of matroids and the minimum rank among the client-side matroids. We apply this algorithm to obtain fixed-parameter algorithms for social network analysis, line planning in public transport, and team management. We complement our tractability results by lower bounds.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset