License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.55
URN: urn:nbn:de:0030-drops-146360
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14636/
Go to the corresponding LIPIcs Volume Portal

Kellerhals, Leon ; Renken, Malte ; Zschoche, Philipp

Parameterized Algorithms for Diverse Multistage Problems

pdf-format:
LIPIcs-ESA-2021-55.pdf (0.8 MB)

Abstract

The world is rarely static - many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the multistage view on computational problems. We study the diverse multistage variant, where consecutive solutions of large variety are preferable to similar ones, e.g. for reasons of fairness or wear minimization. While some aspects of this model have been tackled before, we introduce a framework allowing us to prove that a number of diverse multistage problems are fixed-parameter tractable by diversity, namely Perfect Matching, s-t Path, Matroid Independent Set, and Plurality Voting. This is achieved by first solving special, colored variants of these problems, which might also be of independent interest.

BibTeX - Entry

@InProceedings{kellerhals_et_al:LIPIcs.ESA.2021.55,
  author =	{Kellerhals, Leon and Renken, Malte and Zschoche, Philipp},
  title =	{{Parameterized Algorithms for Diverse Multistage Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14636},
  URN =		{urn:nbn:de:0030-drops-146360},
  doi =		{10.4230/LIPIcs.ESA.2021.55},
  annote =	{Keywords: Temporal graphs, dissimilar solutions, fixed-parameter tractability, perfect matchings, s-t paths, committee election, spanning forests, matroids}
}

Keywords: Temporal graphs, dissimilar solutions, fixed-parameter tractability, perfect matchings, s-t paths, committee election, spanning forests, matroids
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI