2 Search Results for "Bindewald, Viktor"

Document
DOI: 10.4230/LIPIcs.STACS.2019.38
How to Secure Matchings Against Edge Failures

Authors: Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum cost edge-set to the graph, such that the adversary never wins. We show that this problem is equivalent to covering a digraph with non-trivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log_2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general non-negative weights we give tight upper and lower approximation bounds relative to the Directed Steiner Forest problem. Additionally we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical Strong Connectivity Augmentation problem as well as directed Steiner problems.
Cite as

Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. How to Secure Matchings Against Edge Failures. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2019.38,
  author =	{Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver},
  title =	{{How to Secure Matchings Against Edge Failures}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.38},
  URN =		{urn:nbn:de:0030-drops-102772},
  doi =		{10.4230/LIPIcs.STACS.2019.38},
  annote =	{Keywords: Matchings, Robustness, Connectivity Augmentation, Graph Algorithms, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.71
Robust Assignments via Ear Decompositions and Randomized Rounding

Authors: David Adjiashvili, Viktor Bindewald, and Dennis Michaels

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Many real-life planning problems require making a priori decisions before all parameters of the problem have been revealed. An important special case of such problem arises in scheduling and transshipment problems, where a set of jobs needs to be assigned to the available set of machines or personnel (resources), in a way that all jobs have assigned resources, and no two jobs share the same resource. In its nominal form, the resulting computational problem becomes the assignment problem. This paper deals with the Robust Assignment Problem (RAP) which models situations in which certain assignments are vulnerable and may become unavailable after the solution has been chosen. The goal is to choose a minimum-cost collection of assignments (edges in the corresponding bipartite graph) so that if any vulnerable edge becomes unavailable, the remaining part of the solution contains an assignment of all jobs. We develop algorithms and hardness results for RAP and establish several connections to well-known concepts from matching theory, robust optimization, LP-based techniques and combinations thereof.
Cite as

David Adjiashvili, Viktor Bindewald, and Dennis Michaels. Robust Assignments via Ear Decompositions and Randomized Rounding. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.ICALP.2016.71,
  author =	{Adjiashvili, David and Bindewald, Viktor and Michaels, Dennis},
  title =	{{Robust Assignments via Ear Decompositions and Randomized Rounding}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.71},
  URN =		{urn:nbn:de:0030-drops-62133},
  doi =		{10.4230/LIPIcs.ICALP.2016.71},
  annote =	{Keywords: robust optimization, matching theory, ear decomposition, randomized rounding, approximation algorithm}
}
  • Refine by Author
  • 1 Adjiashvili, David
  • 1 Bindewald, Viktor
  • 1 Hommelsheim, Felix
  • 1 Michaels, Dennis
  • 1 Mühlenthaler, Moritz
  • Show More...

  • Refine by Classification
  • 1 Hardware → Robustness
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Matchings and factors
  • 1 Mathematics of computing → Mathematical optimization
  • Show More...

  • Refine by Keyword
  • 1 Connectivity Augmentation
  • 1 Graph Algorithms
  • 1 Matchings
  • 1 Robustness
  • 1 Treewidth
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact