@incollection{BTZ19,
  author =	 {Ren{\'{e}} van Bevern and Oxana Tsidulko and Philipp
                  Zschoche},
  year =	 "2019",
  pages =	 "62--74",
  title =	 {Fixed-parameter algorithms for maximum-profit
                  facility location under matroid constraints},
  editor =	 {Pinar Heggernes},
  booktitle =	 {CIAC 2019},
  series =	 {Lecture Notes in Computer Science},
  publisher =	 {Springer},
  volume =	 {11485},
  date =	 {2019-05-27},
  doi =		 {10.1007/978-3-030-17402-6_6},
  abstract =	 {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.}
}

{"_id":"PEfRf54s9oJH8pp5r","bibbaseid":"vanbevern-tsidulko-zschoche-fixedparameteralgorithmsformaximumprofitfacilitylocationundermatroidconstraints-2019","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Tsidulko, O.","Zschoche, P."],"bibdata":{"bibtype":"incollection","type":"incollection","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Oxana"],"propositions":[],"lastnames":["Tsidulko"],"suffixes":[]},{"firstnames":["Philipp"],"propositions":[],"lastnames":["Zschoche"],"suffixes":[]}],"year":"2019","pages":"62–74","title":"Fixed-parameter algorithms for maximum-profit facility location under matroid constraints","editor":[{"firstnames":["Pinar"],"propositions":[],"lastnames":["Heggernes"],"suffixes":[]}],"booktitle":"CIAC 2019","series":"Lecture Notes in Computer Science","publisher":"Springer","volume":"11485","date":"2019-05-27","doi":"10.1007/978-3-030-17402-6_6","abstract":"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.","bibtex":"@incollection{BTZ19,\n author =\t {Ren{\\'{e}} van Bevern and Oxana Tsidulko and Philipp\n Zschoche},\n year =\t \"2019\",\n pages =\t \"62--74\",\n title =\t {Fixed-parameter algorithms for maximum-profit\n facility location under matroid constraints},\n editor =\t {Pinar Heggernes},\n booktitle =\t {CIAC 2019},\n series =\t {Lecture Notes in Computer Science},\n publisher =\t {Springer},\n volume =\t {11485},\n date =\t {2019-05-27},\n doi =\t\t {10.1007/978-3-030-17402-6_6},\n abstract =\t {We consider a variant of the matroid median problem\n introduced by Krishnaswamy et al. [SODA 2011]: an\n uncapacitated discrete facility location problem\n where the task is to decide which facilities to open\n and which clients to serve for maximum profit so\n that the facilities form an independent set in given\n facility-side matroids and the clients form an\n independent set in given client-side matroids. We\n show that the problem is fixed-parameter tractable\n parameterized by the number of matroids and the\n minimum rank among the client-side matroids. To this\n end, we derive fixed-parameter algorithms for\n computing representative families for matroid\n intersections and maximum-weight set packings with\n multiple matroid constraints. To illustrate the\n modeling capabilities of the new problem, we use it\n to obtain algorithms for a problem in social network\n analysis. We complement our tractability results by\n lower bounds.}\n}\n\n\n","author_short":["van Bevern, R.","Tsidulko, O.","Zschoche, P."],"editor_short":["Heggernes, P."],"key":"BTZ19","id":"BTZ19","bibbaseid":"vanbevern-tsidulko-zschoche-fixedparameteralgorithmsformaximumprofitfacilitylocationundermatroidconstraints-2019","role":"author","urls":{},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":2,"html":""},"bibtype":"incollection","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:24:56.566Z","downloads":2,"keywords":[],"search_terms":["fixed","parameter","algorithms","maximum","profit","facility","location","under","matroid","constraints","van bevern","tsidulko","zschoche"],"title":"Fixed-parameter algorithms for maximum-profit facility location under matroid constraints","year":2019,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}