2 Search Results for "Fischer, Gerhard"

Document
DOI: 10.4230/LIPIcs.IPEC.2021.19
An Investigation of the Recoverable Robust Assignment Problem

Authors: Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2-k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.
Cite as

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. An Investigation of the Recoverable Robust Assignment Problem. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
  author =	{Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
  title =	{{An Investigation of the Recoverable Robust Assignment Problem}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154025},
  doi =		{10.4230/LIPIcs.IPEC.2021.19},
  annote =	{Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
Document
DOI: 10.4230/DagSemProc.07081.20
Meta-Design: A Conceptual Framework for End-User Software Engineering

Authors: Gerhard Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 7081, End-User Software Engineering (2007)

Abstract
In a world that is not predictable, improvisation, evolution, and innovation are more than a luxury: they are a necessity. The challenge of design is not a matter of getting rid of the emergent, but rather of including it and making it an opportunity for more creative and more adequate solutions to problems. Meta-design is an emerging conceptual framework aimed at defining and creating social and technical infrastructures in which new forms of collaborative design can take place. It extends the traditional notion of system design beyond the original development of a system. It is grounded in the basic assumption that future uses and problems cannot be completely anticipated at design time, when a system is developed. Users, at use time, will discover mismatches between their needs and the support that an existing system can provide for them. These mismatches will lead to breakdowns that serve as potential sources of new insights, new knowledge, and new understanding.
Cite as

Gerhard Fischer. Meta-Design: A Conceptual Framework for End-User Software Engineering. In End-User Software Engineering. Dagstuhl Seminar Proceedings, Volume 7081, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fischer:DagSemProc.07081.20,
  author =	{Fischer, Gerhard},
  title =	{{Meta-Design: A Conceptual Framework for End-User Software Engineering}},
  booktitle =	{End-User Software Engineering},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7081},
  editor =	{Margaret H. Burnett and Gregor Engels and Brad A. Myers and Gregg Rothermel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07081.20},
  URN =		{urn:nbn:de:0030-drops-10870},
  doi =		{10.4230/DagSemProc.07081.20},
  annote =	{Keywords: Meta-design, consumers and designers, unself-conscious cultures of design}
}
  • Refine by Author
  • 1 Fischer, Dennis
  • 1 Fischer, Gerhard
  • 1 Hartmann, Tim A.
  • 1 Lendl, Stefan
  • 1 Woeginger, Gerhard J.

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Meta-design
  • 1 RNC
  • 1 assignment problem
  • 1 consumers and designers
  • 1 exact matching
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2007
  • 1 2021

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