Refine
Year of publication
Has Fulltext
- yes (25)
Keywords
- MINT (4)
- Mathematische Modellierung (4)
- Schule (4)
- Multiobjective optimization (3)
- Approximation (2)
- Hypervolume (2)
- Subset selection (2)
- combinatorial optimization (2)
- connectedness (2)
- k-link shortest path (2)
Faculty / Organisational entity
Das MINT-EC-Girls-Camp: Math-Talent-School richtet sich an mathematikbegeisterte Schülerinnen von MINT-EC-Schulen, die Einblicke in die Berufswelt von Mathematikerinnen und Mathematikern bekommen möchten. Die Veranstaltung veranschaulicht den Schülerinnen die steigende Relevanz angewandter mathematischer Forschungsgebiete, wie der Techno- und der Wirtschaftsmathematik. Sie soll dazu dienen, Schüler:innen die Bedeutung mathematischer Arbeitsweisen in der heutigen Berufswelt, insbesondere in Industrie und Wirtschaft, begreifbar zu machen. Die Talent-School wird organisiert von MINT-EC und dem Felix-Klein-Zentrum für Mathematik. Die fachwissenschaftliche Betreuung der Schülerinnen während dieser Talent-School wurde durch Mitarbeitende des Kompetenzzentrums für Mathematische Modellierung in MINT-Projekten in der Schule (KOMMS) der TU Kaiserslautern und des Fraunhofer ITWM umgesetzt. In diesem Report beschreiben wir die Projekte, die während der Talent-School im Oktober 2022 durchgeführt wurden.
Seit 1993 veranstaltet der Fachbereich Mathematik der TU Kaiserslautern jährlich die mathematischen Modellierungswochen. Die Veranstaltung erwuchs parallel zu der steigenden Relevanz angewandter mathematischer Forschungsgebiete, wie der Technomathematik und der Wirtschaftsmathematik. Sie soll dazu dienen, Schülerinnen und Schülern die Bedeutung mathematischer Arbeitsweisen in der heutigen Berufswelt, insbesondere in Industrie und Wirtschaft, begreifbar zu machen. Darüber hinaus bietet die Modellierungswoche den teilnehmenden Lehrkräften einen Einblick in die Projektarbeit mit offenen Fragestellungen im Rahmen der mathematischen Modellierung. In diesem Report beschreiben wir die Projekte, die während der Modellierungswoche im Dezember 2021 durchgeführt wurden. Der Themenschwerpunkt der Veranstaltung lautete "Wetter und Katastrophenschutz".
In a widely-studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. Then, the goal is to provide an optimal solution set, i.e., a set containing an optimal solution for each non-parametric problem obtained by fixing a parameter vector. For many multi-parametric optimization problems, however, an optimal solution set of minimum cardinality can contain super-polynomially many solutions. Consequently, no polynomial-time exact algorithms can exist for these problems even if P=NP. We propose an approximation method that is applicable to a general class of multi-parametric optimization problems and outputs a set of solutions with cardinality polynomial in the instance size and the inverse of the approximation guarantee. This method lifts approximation algorithms for non-parametric optimization problems to their parametric version and provides an approximation guarantee that is arbitrarily close to the approximation guarantee of the approximation algorithm for the non-parametric problem. If the non-parametric problem can be solved exactly in polynomial time or if an FPTAS is available, our algorithm is an FPTAS. Further, we show that, for any given approximation guarantee, the minimum cardinality of an approximation set is, in general, not ℓ-approximable for any natural number ℓ less or equal to the number of parameters, and we discuss applications of our results to classical multi-parametric combinatorial optimizations problems. In particular, we obtain an FPTAS for the multi-parametric minimum s-t-cut problem, an FPTAS for the multi-parametric knapsack problem, as well as an approximation algorithm for the multi-parametric maximization of independence systems problem.
Many real-world optimization and decision-making problems comprise several, partly conflicting objective functions. The English saying “Quality has its price” is just as true on a large scale as it is in private sphere and, therefore, quality and price are a typical pair of conflicting objective functions that are very common in applications. Yet, in industrial applications, both quality and cost may be understood in the specific context and differ whether a transportation, a production, or a planning problem is considered. Other objective functions that are receiving increasing attention in real-world decision-making situations are, for example, robustness, time, sustainability, adaptability, or longevity.
This article investigates a network interdiction problem on a tree network: given a subset of nodes chosen as facilities, an interdictor may dissect the network by removing a size-constrained set of edges, striving to worsen the established facilities best possible. Here, we consider a reachability objective function, which is closely related to the covering objective function: the interdictor aims to minimize the number of customers that are still connected to any facility after interdiction. For the covering objective on general graphs, this problem is known to be NP-complete (Fröhlich and Ruzika In: On the hardness of covering-interdiction problems. Theor. Comput. Sci., 2021). In contrast to this, we propose a polynomial-time solution algorithm to solve the problem on trees. The algorithm is based on dynamic programming and reveals the relation of this location-interdiction problem to knapsack-type problems. However, the input data for the dynamic program must be elaborately generated and relies on the theoretical results presented in this article. As a result, trees are the first known graph class that admits a polynomial-time algorithm for edge interdiction problems in the context of facility location planning.
Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the
Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time
solvability of a certain auxiliary problem determines the class of multiobjective optimization
problems that admit a polynomial-time computable (1+ε, . . . , 1+ε)-approximate Pareto set
(also called an ε-Pareto set). Similarly, in this article, we characterize the class ofmultiobjective
optimization problems having a polynomial-time computable approximate ε-Pareto set
that is exact in one objective by the efficient solvability of an appropriate auxiliary problem.
This class includes important problems such as multiobjective shortest path and spanning
tree, and the approximation guarantee we provide is, in general, best possible. Furthermore,
for biobjective optimization problems from this class, we provide an algorithm that computes
a one-exact ε-Pareto set of cardinality at most twice the cardinality of a smallest such set and
show that this factor of 2 is best possible. For three or more objective functions, however,
we prove that no constant-factor approximation on the cardinality of the set can be obtained
efficiently.
This article is dedicated to the weight set decomposition of a multiobjective (mixed-)integer linear problem with three objectives. We propose an algorithm that returns a decomposition of the parameter set of the weighted sum scalarization by solving biobjective subproblems via Dichotomic Search which corresponds to a line exploration in the weight set. Additionally, we present theoretical results regarding the boundary of the weight set components that direct the line exploration. The resulting algorithm runs in output polynomial time, i.e. its running time is polynomial in the encoding length of both the input and output. Also, the proposed approach can be used for each weight set component individually and is able to give intermediate results, which can be seen as an “approximation” of the weight set component. We compare the running time of our method with the one of an existing algorithm and conduct a computational study that shows the competitiveness of our algorithm. Further, we give a state-of-the-art survey of algorithms in the literature.
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignment problem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a method for lifting approximation algorithms for non-parametric optimization problems to their parametric counterparts that is applicable to a general class of parametric optimization problems. The approximation guarantee achieved by this method for a parametric problem is arbitrarily close to the approximation guarantee of the algorithm for the corresponding non-parametric problem. It outputs polynomially many solutions and has polynomial running time if the non-parametric algorithm has polynomial running time. In the case that the non-parametric problem can be solved exactly in polynomial time or that an FPTAS is available, the method yields an FPTAS. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above and a (3/2 + ε) -approximation algorithm for the parametric metric traveling salesman problem. Moreover, we describe a post-processing procedure that, if the non-parametric problem can be solved exactly in polynomial time, further decreases the number of returned solutions such that the method outputs at most twice as many solutions as needed at minimum for achieving the desired approximation guarantee.
Die MINT-EC-Girls-Camp: Math-Talent-School ist eine vom Fraunhofer Institut für Techno- und Wirtschaftsmathematik (ITWM) initiierte Veranstaltung, die regelmäßig als Kooperation zwischen dem Felix-Klein-Zentrum für Mathematik und dem Verein mathematisch-naturwissenschaftlicher Excellence-Center an Schulen e.V. (Verein MINT-EC) durchgeführt wird. Die methodisch-didaktische Konzeption der Math-Talent-Schools erfolgt durch das Kompetenzzentrum für Mathematische Modellierung in MINT-Projekten in der Schule (KOMMS), einer wissenschaftlichen Einrichtung des Fachbereichs Mathematik der Technischen Universität Kaiserslautern. Die inhaltlich-organisatorische Ausführung übernimmt das Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM in enger Abstimmung und Kooperation von Wissenschaftlern der Technischen Universität und des Fraunhofer ITWM. Die MINT-EC-Girls-Camp: Math-Talent-School hat zum Ziel, Mathematik-interessierten Schülerinnen einen Einblick in die Arbeitswelt von Mathematikerinnen und Mathematikern zu geben. In diesem Artikel stellen wir die Math-Talent-School vor. Hierfür werden die fachlichen und fachdidaktischen Hintergründe der Projekte beleuchtet, der Ablauf der Veranstaltung erläutert und ein Fazit gezogen.
Dieser Beitrag beschreibt eine Lernumgebung für Schülerinnen und Schüler der Unter- und Mittelstufe mit einem Schwerpunkt im Fach Mathematik. Das Thema dieser Lernumgebung ist die Simulation von Entfluchtungsprozessen im Rahmen von Gebäudeevakuierungen. Dabei wird das Konzept eines zellulären Automaten vermittelt, ohne dabei Programmierkenntnisse vorauszusetzen oder anzuwenden. Anhand dieses speziellen Simulationswerkzeugs des zellulären Automaten werden Eigenschaften, Kenngrößen sowie Vor- und Nachteile von Simulationen im Allgemeinen thematisiert. Dazu gehören unter anderem die experimentelle Datengewinnung, die Festlegung von Modellparametern, die Diskretisierung des zeitlichen und räumlichen Betrachtungshorizonts sowie die zwangsläufig auftretenden (Diskretisierungs-)Fehler, die algorithmischen Abläufe einer Simulation in Form elementarer Handlungsanweisungen, die Speicherung und Visualisierung von Daten aus einer Simulation sowie die Interpretation und kritische Diskussion von Simulationsergebnissen. Die vorgestellte Lernumgebung ermöglicht etliche Variationen zu weiteren Aspekten des Themas „Evakuierungssimulation“ und bietet dadurch auch vielfältige Differenzierungsmöglichkeiten.