## René van Bevern, Oxana Yu. Tsidulko, and Philipp Zschoche.
Fixed-parameter algorithms for maximum-profit facility location under
matroid constraints.
2019.

We consider a variant of the matroid median problem
introduced by Krishnaswamy et al. [SODA 2011]: an
uncapacitated discrete facility location problem
where 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. We
show that the problem is fixed-parameter tractable
parameterized by the number of matroids and the
minimum rank among the client-side matroids. To this
end, we derive fixed-parameter algorithms for
computing representative families for matroid
intersections and maximum-weight set packings with
multiple matroid constraints. To illustrate the
modeling capabilities of the new problem, we use it
to obtain algorithms for a problem in social network
analysis. We complement our tractability results by
lower bounds.

[ bib |
http ]
Back

*This file was generated by
bibtex2html 1.98.*