Zusammenfassung
Mitarbeitende einer Bank begleiten Sehbehinderte zu einem Konzert, Telekommunikationsfachleute verbringen einen Tag mit manisch-depressiven Personen in der Werkstatt: Corporate ...Volunteering (CV) gewinnt zunehmend an Bedeutung. Wie nehmen betroffene KlientInnen sozialer Nonprofit-Organisationen (NPO) diese Einsätze wahr und ist der Austausch mit Unternehmensmitarbeitenden tatsächlich ein Mehrwert für sie (wie die Theorie behauptet)?
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β-triangle inequality. A reoptimization algorithm exploits the knowledge of an ...optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and 1+γ for an arbitrary small γ>0), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them.
As for the upper bounds, for some local modifications, we design linear-time (1/2+β)-approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs (β=1), none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2β-approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any β<1/2+ln(3)/4≈0.775.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β -triangle inequality. A reoptimization algorithm exploits the knowledge of an ...optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and 1+ γ for an arbitrary small γ > 0), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them. As for the upper bounds, for some local modifications, we design linear-time (1 / 2 + β )-approximation algorithms, and even polynomialtime approximation schemes, whereas for metric graphs ( β = 1), none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2 β -approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any β < 1 / 2 + ln(3) / 4 ≈ 0 . 775.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The main goal of this paper is to present our approach for writing textbooks that are self-contained and available for individual learning. These texts are written in the language of the ...corresponding pupils and are not restricted by any length limitations. This allows us to write as clearly and thoroughly as possible. Minimizing the time for mastering the subject instead of minimizing the presentation length is the main goal. The detailed lecture notes provide a safety net for the teacher and the pupils alike. They do not restrict teachers in their interaction with the class or in the freedom of choosing alternative ways in approaching the subject. On the contrary, the freedom of designing the content of the lesson increases because pupils have the certainty to be able to learn from the lecture notes if something was not fully understood.
Here some general rules for writing learning aids are presented and then applied for an introductory course about programming in LOGO. Finally, we summarize our teaching experience in different classes with the produced learning aids.
In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β-triangle inequality. A reoptimization algorithm exploits the knowledge of an ...optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and 1 + γ for an arbitrary small γ> 0), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them.
As for the upper bounds, for some local modifications, we design linear-time (1/2 + β)-approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs (β= 1), none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2β-approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any β < 1/2 + ln (3)/4 ≈ 0.775.
PDF
