---
_id: '36060'
abstract:
- lang: eng
text: 'Merging a sample of 492 merger and acquisition (M&A) announcements from 284
acquiring firms across Europe and North America with data from 5-year single-name
credit default swaps (CDSs) written on stock-listed acquiring firms between 2005
and 2018, the paper at hand empirically analyzes the CDS investors’ risk perceptions
of M&A announcements using event study methodologies. As a baseline result, we
provide evidence for significantly positive cumulative average abnormal CDS spread
changes for both, European and North American acquirers suggesting that CDS investors
perceive an increase in the acquiring firms’ credit risk exposures due to M&A
announcements. Our baseline finding holds under several robustness checks, especially
when controlling for the robustness of the empirical design. Moreover, results
from a large variety of sensitivity analyses reveal a number of deal and firm
characteristics that may explain why CDS investors from our sample expect an increase
in the acquirers’ credit risk exposures due to forthcoming M&A transactions. '
author:
- first_name: Benjamin
full_name: Hippert, Benjamin
last_name: Hippert
- first_name: André
full_name: Uhde, André
id: '36049'
last_name: Uhde
citation:
ama: Hippert B, Uhde A. CDS Investors’ Risk Perceptions of M&A Announcements.
apa: Hippert, B., & Uhde, A. (n.d.). CDS Investors’ Risk Perceptions of M&A
Announcements.
bibtex: '@book{Hippert_Uhde, title={CDS Investors’ Risk Perceptions of M&A Announcements},
author={Hippert, Benjamin and Uhde, André} }'
chicago: Hippert, Benjamin, and André Uhde. CDS Investors’ Risk Perceptions of
M&A Announcements, n.d.
ieee: B. Hippert and A. Uhde, CDS Investors’ Risk Perceptions of M&A Announcements.
.
mla: Hippert, Benjamin, and André Uhde. CDS Investors’ Risk Perceptions of M&A
Announcements.
short: B. Hippert, A. Uhde, CDS Investors’ Risk Perceptions of M&A Announcements,
n.d.
date_created: 2023-01-11T11:31:54Z
date_updated: 2023-11-17T10:23:54Z
department:
- _id: '186'
- _id: '188'
jel:
- G14
- G34
keyword:
- credit default swaps
- risk perception of CDS investors
- mergers and acquisitions
- event study
language:
- iso: eng
publication_status: unpublished
status: public
title: CDS Investors’ Risk Perceptions of M&A Announcements
type: working_paper
user_id: '36049'
year: '2021'
...
---
_id: '36063'
abstract:
- lang: eng
text: "This paper empirically investigates determinants of the outstanding net notional
amount\r\nof credit default swaps (CDSs) contracts written on banks. We extend
and complement the\r\nprevious literature dealing with CDS trading by analyzing
a comprehensive set of CDS tradingspecific,\r\nbank-fundamental, macroeconomic
and bank-institutional determinants. We find that\r\nrisk hedging clearly dominates
an investor’s speculation and arbitrage motive, while the latter,\r\nhowever,
exhibits the strongest impact on the outstanding net notional amount of bank CDSs.\r\nFurthermore,
being classified as a G-SIB, being a constituent of the main CDS index and the\r\nequity
trading volume may significantly explain changes in the outstanding CDS net notional
on\r\nbanks. The analysis at hand provides important implications for both academics
and practitioners,\r\nsince understanding the trading motives of bank CDS investors
provides a deeper insight into the\r\nopaque CDS market. "
author:
- first_name: Benjamin
full_name: Hippert, Benjamin
last_name: Hippert
- first_name: André
full_name: Uhde, André
id: '36049'
last_name: Uhde
- first_name: Sascha Tobias
full_name: Wengerek, Sascha Tobias
last_name: Wengerek
citation:
ama: Hippert B, Uhde A, Wengerek ST. Determinants of CDS Trading on Major Banks.
apa: Hippert, B., Uhde, A., & Wengerek, S. T. (n.d.). Determinants of CDS
Trading on Major Banks.
bibtex: '@book{Hippert_Uhde_Wengerek, title={Determinants of CDS Trading on Major
Banks}, author={Hippert, Benjamin and Uhde, André and Wengerek, Sascha Tobias}
}'
chicago: Hippert, Benjamin, André Uhde, and Sascha Tobias Wengerek. Determinants
of CDS Trading on Major Banks, n.d.
ieee: B. Hippert, A. Uhde, and S. T. Wengerek, Determinants of CDS Trading on
Major Banks. .
mla: Hippert, Benjamin, et al. Determinants of CDS Trading on Major Banks.
short: B. Hippert, A. Uhde, S.T. Wengerek, Determinants of CDS Trading on Major
Banks, n.d.
date_created: 2023-01-11T11:34:17Z
date_updated: 2023-11-17T10:23:44Z
department:
- _id: '186'
- _id: '188'
jel:
- G10
- G12
- G21
keyword:
- banking
- outstanding CDS net notional
- determinants of bank CDS trading
language:
- iso: eng
publication_status: unpublished
status: public
title: Determinants of CDS Trading on Major Banks
type: working_paper
user_id: '36049'
year: '2021'
...
---
_id: '29308'
abstract:
- lang: eng
text: 'In this paper we present our system for the Detection and Classification
of Acoustic Scenes and Events (DCASE) 2021 Challenge Task 4: Sound Event Detection
and Separation in Domestic Environments, where it scored the fourth rank. Our
presented solution is an advancement of our system used in the previous edition
of the task.We use a forward-backward convolutional recurrent neural network (FBCRNN)
for tagging and pseudo labeling followed by tag-conditioned sound event detection
(SED) models which are trained using strong pseudo labels provided by the FBCRNN.
Our advancement over our earlier model is threefold. First, we introduce a strong
label loss in the objective of the FBCRNN to take advantage of the strongly labeled
synthetic data during training. Second, we perform multiple iterations of self-training
for both the FBCRNN and tag-conditioned SED models. Third, while we used only
tag-conditioned CNNs as our SED model in the previous edition we here explore
sophisticated tag-conditioned SED model architectures, namely, bidirectional CRNNs
and bidirectional convolutional transformer neural networks (CTNNs), and combine
them. With metric and class specific tuning of median filter lengths for post-processing,
our final SED model, consisting of 6 submodels (2 of each architecture), achieves
on the public evaluation set poly-phonic sound event detection scores (PSDS) of
0.455 for scenario 1 and 0.684 for scenario as well as a collar-based F1-score
of 0.596 outperforming the baselines and our model from the previous edition by
far. Source code is publicly available at https://github.com/fgnt/pb_sed.'
author:
- first_name: Janek
full_name: Ebbers, Janek
id: '34851'
last_name: Ebbers
- first_name: Reinhold
full_name: Haeb-Umbach, Reinhold
id: '242'
last_name: Haeb-Umbach
citation:
ama: 'Ebbers J, Haeb-Umbach R. Self-Trained Audio Tagging and Sound Event Detection
in Domestic Environments. In: Proceedings of the 6th Detection and Classification
of Acoustic Scenes and Events 2021 Workshop (DCASE2021). ; 2021:226–230.'
apa: Ebbers, J., & Haeb-Umbach, R. (2021). Self-Trained Audio Tagging and Sound
Event Detection in Domestic Environments. Proceedings of the 6th Detection
and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021),
226–230.
bibtex: '@inproceedings{Ebbers_Haeb-Umbach_2021, place={Barcelona, Spain}, title={Self-Trained
Audio Tagging and Sound Event Detection in Domestic Environments}, booktitle={Proceedings
of the 6th Detection and Classification of Acoustic Scenes and Events 2021 Workshop
(DCASE2021)}, author={Ebbers, Janek and Haeb-Umbach, Reinhold}, year={2021}, pages={226–230}
}'
chicago: Ebbers, Janek, and Reinhold Haeb-Umbach. “Self-Trained Audio Tagging and
Sound Event Detection in Domestic Environments.” In Proceedings of the 6th
Detection and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021),
226–230. Barcelona, Spain, 2021.
ieee: J. Ebbers and R. Haeb-Umbach, “Self-Trained Audio Tagging and Sound Event
Detection in Domestic Environments,” in Proceedings of the 6th Detection and
Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021), 2021,
pp. 226–230.
mla: Ebbers, Janek, and Reinhold Haeb-Umbach. “Self-Trained Audio Tagging and Sound
Event Detection in Domestic Environments.” Proceedings of the 6th Detection
and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021),
2021, pp. 226–230.
short: 'J. Ebbers, R. Haeb-Umbach, in: Proceedings of the 6th Detection and Classification
of Acoustic Scenes and Events 2021 Workshop (DCASE2021), Barcelona, Spain, 2021,
pp. 226–230.'
date_created: 2022-01-13T08:07:47Z
date_updated: 2023-11-22T08:28:32Z
ddc:
- '000'
department:
- _id: '54'
file:
- access_level: open_access
content_type: application/pdf
creator: ebbers
date_created: 2022-01-13T08:08:54Z
date_updated: 2022-01-13T08:19:50Z
file_id: '29309'
file_name: template.pdf
file_size: 239462
relation: main_file
file_date_updated: 2022-01-13T08:19:50Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 226–230
place: Barcelona, Spain
project:
- _id: '52'
name: 'PC2: Computing Resources Provided by the Paderborn Center for Parallel Computing'
publication: Proceedings of the 6th Detection and Classification of Acoustic Scenes
and Events 2021 Workshop (DCASE2021)
publication_identifier:
isbn:
- 978-84-09-36072-7
quality_controlled: '1'
status: public
title: Self-Trained Audio Tagging and Sound Event Detection in Domestic Environments
type: conference
user_id: '34851'
year: '2021'
...
---
_id: '29306'
abstract:
- lang: eng
text: Recently, there has been a rising interest in sound recognition via Acoustic
Sensor Networks to support applications such as ambient assisted living or environmental
habitat monitoring. With state-of-the-art sound recognition being dominated by
deep-learning-based approaches, there is a high demand for labeled training data.
Despite the availability of large-scale data sets such as Google's AudioSet,
acquiring training data matching a certain application environment is still often
a problem. In this paper we are concerned with human activity monitoring in a
domestic environment using an ASN consisting of multiple nodes each providing
multichannel signals. We propose a self-training based domain adaptation approach,
which only requires unlabeled data from the target environment. Here, a sound
recognition system trained on AudioSet, the teacher, generates pseudo labels for
data from the target environment on which a student network is trained. The student
can furthermore glean information about the spatial arrangement of sensors and
sound sources to further improve classification performance. It is shown that the
student significantly improves recognition performance over the pre-trained teacher
without relying on labeled data from the environment the system is deployed in.
author:
- first_name: Janek
full_name: Ebbers, Janek
id: '34851'
last_name: Ebbers
- first_name: Moritz Curt
full_name: Keyser, Moritz Curt
last_name: Keyser
- first_name: Reinhold
full_name: Haeb-Umbach, Reinhold
id: '242'
last_name: Haeb-Umbach
citation:
ama: 'Ebbers J, Keyser MC, Haeb-Umbach R. Adapting Sound Recognition to A New Environment
Via Self-Training. In: Proceedings of the 29th European Signal Processing Conference
(EUSIPCO). ; 2021:1135–1139.'
apa: Ebbers, J., Keyser, M. C., & Haeb-Umbach, R. (2021). Adapting Sound Recognition
to A New Environment Via Self-Training. Proceedings of the 29th European Signal
Processing Conference (EUSIPCO), 1135–1139.
bibtex: '@inproceedings{Ebbers_Keyser_Haeb-Umbach_2021, title={Adapting Sound Recognition
to A New Environment Via Self-Training}, booktitle={Proceedings of the 29th European
Signal Processing Conference (EUSIPCO)}, author={Ebbers, Janek and Keyser, Moritz
Curt and Haeb-Umbach, Reinhold}, year={2021}, pages={1135–1139} }'
chicago: Ebbers, Janek, Moritz Curt Keyser, and Reinhold Haeb-Umbach. “Adapting
Sound Recognition to A New Environment Via Self-Training.” In Proceedings of
the 29th European Signal Processing Conference (EUSIPCO), 1135–1139, 2021.
ieee: J. Ebbers, M. C. Keyser, and R. Haeb-Umbach, “Adapting Sound Recognition to
A New Environment Via Self-Training,” in Proceedings of the 29th European Signal
Processing Conference (EUSIPCO), 2021, pp. 1135–1139.
mla: Ebbers, Janek, et al. “Adapting Sound Recognition to A New Environment Via
Self-Training.” Proceedings of the 29th European Signal Processing Conference
(EUSIPCO), 2021, pp. 1135–1139.
short: 'J. Ebbers, M.C. Keyser, R. Haeb-Umbach, in: Proceedings of the 29th European
Signal Processing Conference (EUSIPCO), 2021, pp. 1135–1139.'
date_created: 2022-01-13T08:01:21Z
date_updated: 2023-11-22T08:28:50Z
ddc:
- '000'
department:
- _id: '54'
file:
- access_level: open_access
content_type: application/pdf
creator: ebbers
date_created: 2022-01-13T08:03:26Z
date_updated: 2022-01-13T08:19:35Z
file_id: '29307'
file_name: conference_101719.pdf
file_size: 213938
relation: main_file
file_date_updated: 2022-01-13T08:19:35Z
has_accepted_license: '1'
language:
- iso: eng
oa: '1'
page: 1135–1139
project:
- _id: '52'
name: 'PC2: Computing Resources Provided by the Paderborn Center for Parallel Computing'
publication: Proceedings of the 29th European Signal Processing Conference (EUSIPCO)
quality_controlled: '1'
status: public
title: Adapting Sound Recognition to A New Environment Via Self-Training
type: conference
user_id: '34851'
year: '2021'
...
---
_id: '49145'
abstract:
- lang: ger
text: Auch in diesem Semester finden Veranstaltungen im Fach Philosophie an den
meisten Universitäten vor allem online statt; die Pandemie-Lage lässt eine Öffnung
der Unis für Präsenzveranstaltungen kaum zu. Die folgenden Überlegungen hat Sebastian
Luft, Professor an der Marquette University in Milwaukee/WI, aus aktuellem Anlass
verfasst. 2019 erschien sein Buch »Philosophie lehren« zur philosophischen Hochschuldidaktik.
Der folgende Text bietet eine aktuelle Ergänzung zur dortigen Handreichung für
die philosophische Lehre.
author:
- first_name: Sebastian
full_name: Luft, Sebastian
id: '55271'
last_name: Luft
citation:
ama: Luft S. »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige Gedanken
zur digitalen Lehre in der Pandemie. Meiner Telegramm; 2021.
apa: Luft, S. (2021). »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige
Gedanken zur digitalen Lehre in der Pandemie. Meiner Telegramm.
bibtex: '@book{Luft_2021, title={»Wir hören Dich nicht, schalte bitte Dein Mikro
an ! « Einige Gedanken zur digitalen Lehre in der Pandemie.}, publisher={Meiner
Telegramm}, author={Luft, Sebastian}, year={2021} }'
chicago: Luft, Sebastian. »Wir hören Dich nicht, schalte bitte Dein Mikro an !
« Einige Gedanken zur digitalen Lehre in der Pandemie. Meiner Telegramm, 2021.
ieee: S. Luft, »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige
Gedanken zur digitalen Lehre in der Pandemie. Meiner Telegramm, 2021.
mla: Luft, Sebastian. »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige
Gedanken zur digitalen Lehre in der Pandemie. Meiner Telegramm, 2021.
short: S. Luft, »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige Gedanken
zur digitalen Lehre in der Pandemie., Meiner Telegramm, 2021.
date_created: 2023-11-23T09:20:33Z
date_updated: 2023-11-23T09:22:05Z
department:
- _id: '813'
extern: '1'
language:
- iso: ger
main_file_link:
- url: https://meiner.de/media/attachment/file/m/e/meiner_telegramm_2021_04.pdf
page: '7'
publication_status: published
publisher: Meiner Telegramm
status: public
title: »Wir hören Dich nicht, schalte bitte Dein Mikro an ! « Einige Gedanken zur
digitalen Lehre in der Pandemie.
type: misc
user_id: '59882'
year: '2021'
...
---
_id: '49149'
author:
- first_name: Sebastian
full_name: Luft, Sebastian
id: '55271'
last_name: Luft
citation:
ama: Luft S. In Amerika promovieren? Hinweise von Sebastian Luft. Information
Philosophie. 2021;(4).
apa: Luft, S. (2021). In Amerika promovieren? Hinweise von Sebastian Luft. Information
Philosophie, 4.
bibtex: '@article{Luft_2021, title={In Amerika promovieren? Hinweise von Sebastian
Luft}, number={4}, journal={Information Philosophie}, publisher={Claudia Moser
Verlag}, author={Luft, Sebastian}, year={2021} }'
chicago: Luft, Sebastian. “In Amerika promovieren? Hinweise von Sebastian Luft.”
Information Philosophie, no. 4 (2021).
ieee: S. Luft, “In Amerika promovieren? Hinweise von Sebastian Luft,” Information
Philosophie, no. 4, 2021.
mla: Luft, Sebastian. “In Amerika promovieren? Hinweise von Sebastian Luft.” Information
Philosophie, no. 4, Claudia Moser Verlag, 2021.
short: S. Luft, Information Philosophie (2021).
date_created: 2023-11-23T09:35:52Z
date_updated: 2023-11-23T09:36:00Z
department:
- _id: '813'
extern: '1'
issue: '4'
language:
- iso: ger
publication: Information Philosophie
publication_status: published
publisher: Claudia Moser Verlag
related_material:
link:
- relation: confirmation
url: https://www.information-philosophie.de/?a=1&t=9458&n=2
status: public
title: In Amerika promovieren? Hinweise von Sebastian Luft
type: journal_article
user_id: '59882'
year: '2021'
...
---
_id: '47957'
author:
- first_name: Jennifer Nicole
full_name: Schneider, Jennifer Nicole
last_name: Schneider
citation:
ama: 'Schneider JN. Digital transformation in industry. In: Beutner M, Pechuel R,
Schneider J, eds. Fostering Digitisation and Industry 4.0: Education – Vocation
- Industry – Future. New Opportunities and Challenges for European VET. Insights
in the DigI-VET Project. ; 2021:57-62.'
apa: 'Schneider, J. N. (2021). Digital transformation in industry. In M. Beutner,
R. Pechuel, & J. Schneider (Eds.), Fostering Digitisation and Industry
4.0: Education – Vocation - Industry – Future. New Opportunities and Challenges
for European VET. Insights in the DigI-VET Project (pp. 57–62).'
bibtex: '@inbook{Schneider_2021, place={Köln }, title={Digital transformation in
industry}, booktitle={Fostering Digitisation and Industry 4.0: Education – Vocation
- Industry – Future. New Opportunities and Challenges for European VET. Insights
in the DigI-VET Project}, author={Schneider, Jennifer Nicole}, editor={Beutner,
Marc and Pechuel, Rasmus and Schneider, Jennifer }, year={2021}, pages={57–62}
}'
chicago: 'Schneider, Jennifer Nicole. “Digital Transformation in Industry.” In Fostering
Digitisation and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, edited
by Marc Beutner, Rasmus Pechuel, and Jennifer Schneider, 57–62. Köln , 2021.'
ieee: 'J. N. Schneider, “Digital transformation in industry,” in Fostering Digitisation
and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, M. Beutner,
R. Pechuel, and J. Schneider, Eds. Köln , 2021, pp. 57–62.'
mla: 'Schneider, Jennifer Nicole. “Digital Transformation in Industry.” Fostering
Digitisation and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, edited
by Marc Beutner et al., 2021, pp. 57–62.'
short: 'J.N. Schneider, in: M. Beutner, R. Pechuel, J. Schneider (Eds.), Fostering
Digitisation and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, Köln , 2021,
pp. 57–62.'
date_created: 2023-10-11T08:12:55Z
date_updated: 2023-11-29T14:58:37Z
department:
- _id: '208'
editor:
- first_name: 'Marc '
full_name: 'Beutner, Marc '
last_name: Beutner
- first_name: Rasmus
full_name: Pechuel, Rasmus
last_name: Pechuel
- first_name: 'Jennifer '
full_name: 'Schneider, Jennifer '
last_name: Schneider
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://digivet.eduproject.eu/wp-content/uploads/2021/09/DigI-VET-EN.pdf
oa: '1'
page: '57 - 62 '
place: 'Köln '
project:
- _id: '79'
grant_number: '2018-1-DE02-KA202-005145 '
name: 'Digi-VET: Digi-VET: Fostering Digitisation and Industry 4.0 in vocational
education and training '
publication: 'Fostering Digitisation and Industry 4.0: Education – Vocation - Industry
– Future. New Opportunities and Challenges for European VET. Insights in the DigI-VET
Project'
publication_status: published
status: public
title: Digital transformation in industry
type: book_chapter
user_id: '38157'
year: '2021'
...
---
_id: '47966'
author:
- first_name: 'Jennifer '
full_name: 'Schneider, Jennifer '
last_name: Schneider
citation:
ama: 'Schneider J. Teaching and Learning Materials. In: Beutner M, Pechuel R, Schneider
J, eds. Fostering Digitisation and Industry 4.0: Education – Vocation - Industry
– Future. New Opportunities and Challenges for European VET. Insights in the DigI-VET
Project. ; 2021:150-165.'
apa: 'Schneider, J. (2021). Teaching and Learning Materials. In M. Beutner, R. Pechuel,
& J. Schneider (Eds.), Fostering Digitisation and Industry 4.0: Education
– Vocation - Industry – Future. New Opportunities and Challenges for European
VET. Insights in the DigI-VET Project (pp. 150–165).'
bibtex: '@inbook{Schneider_2021, place={Köln }, title={Teaching and Learning Materials},
booktitle={Fostering Digitisation and Industry 4.0: Education – Vocation - Industry
– Future. New Opportunities and Challenges for European VET. Insights in the DigI-VET
Project}, author={Schneider, Jennifer }, editor={Beutner, Marc and Pechuel, Rasmus
and Schneider, Jennifer}, year={2021}, pages={150–165} }'
chicago: 'Schneider, Jennifer . “Teaching and Learning Materials.” In Fostering
Digitisation and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, edited
by Marc Beutner, Rasmus Pechuel, and Jennifer Schneider, 150–65. Köln , 2021.'
ieee: 'J. Schneider, “Teaching and Learning Materials,” in Fostering Digitisation
and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, M. Beutner,
R. Pechuel, and J. Schneider, Eds. Köln , 2021, pp. 150–165.'
mla: 'Schneider, Jennifer. “Teaching and Learning Materials.” Fostering Digitisation
and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, edited
by Marc Beutner et al., 2021, pp. 150–65.'
short: 'J. Schneider, in: M. Beutner, R. Pechuel, J. Schneider (Eds.), Fostering
Digitisation and Industry 4.0: Education – Vocation - Industry – Future. New Opportunities
and Challenges for European VET. Insights in the DigI-VET Project, Köln , 2021,
pp. 150–165.'
date_created: 2023-10-11T08:26:43Z
date_updated: 2023-11-29T14:58:34Z
department:
- _id: '208'
editor:
- first_name: 'Marc '
full_name: 'Beutner, Marc '
last_name: Beutner
- first_name: Rasmus
full_name: Pechuel, Rasmus
last_name: Pechuel
- first_name: Jennifer
full_name: Schneider, Jennifer
last_name: Schneider
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://digivet.eduproject.eu/wp-content/uploads/2021/09/DigI-VET-EN.pdf
oa: '1'
page: 150 - 165
place: 'Köln '
project:
- _id: '79'
grant_number: '2018-1-DE02-KA202-005145 '
name: 'Digi-VET: Digi-VET: Fostering Digitisation and Industry 4.0 in vocational
education and training '
publication: 'Fostering Digitisation and Industry 4.0: Education – Vocation - Industry
– Future. New Opportunities and Challenges for European VET. Insights in the DigI-VET
Project'
publication_status: published
status: public
title: Teaching and Learning Materials
type: book_chapter
user_id: '38157'
year: '2021'
...
---
_id: '24456'
abstract:
- lang: eng
text: One objective of current research in explainable intelligent systems is to
implement social aspects in order to increase the relevance of explanations. In
this paper, we argue that a novel conceptual framework is needed to overcome shortcomings
of existing AI systems with little attention to processes of interaction and learning.
Drawing from research in interaction and development, we first outline the novel
conceptual framework that pushes the design of AI systems toward true interactivity
with an emphasis on the role of the partner and social relevance. We propose that
AI systems will be able to provide a meaningful and relevant explanation only
if the process of explaining is extended to active contribution of both partners
that brings about dynamics that is modulated by different levels of analysis.
Accordingly, our conceptual framework comprises monitoring and scaffolding as
key concepts and claims that the process of explaining is not only modulated by
the interaction between explainee and explainer but is embedded into a larger
social context in which conventionalized and routinized behaviors are established.
We discuss our conceptual framework in relation to the established objectives
of transparency and autonomy that are raised for the design of explainable AI
systems currently.
article_type: original
author:
- first_name: Katharina J.
full_name: Rohlfing, Katharina J.
id: '50352'
last_name: Rohlfing
- first_name: Philipp
full_name: Cimiano, Philipp
last_name: Cimiano
- first_name: Ingrid
full_name: Scharlau, Ingrid
id: '451'
last_name: Scharlau
orcid: 0000-0003-2364-9489
- first_name: Tobias
full_name: Matzner, Tobias
id: '65695'
last_name: Matzner
- first_name: Heike M.
full_name: Buhl, Heike M.
id: '27152'
last_name: Buhl
- first_name: Hendrik
full_name: Buschmeier, Hendrik
last_name: Buschmeier
- first_name: Elena
full_name: Esposito, Elena
last_name: Esposito
- first_name: Angela
full_name: Grimminger, Angela
id: '57578'
last_name: Grimminger
- first_name: Barbara
full_name: Hammer, Barbara
last_name: Hammer
- first_name: Reinhold
full_name: Haeb-Umbach, Reinhold
id: '242'
last_name: Haeb-Umbach
- first_name: Ilona
full_name: Horwath, Ilona
id: '68836'
last_name: Horwath
- first_name: Eyke
full_name: Hüllermeier, Eyke
id: '48129'
last_name: Hüllermeier
- first_name: Friederike
full_name: Kern, Friederike
last_name: Kern
- first_name: Stefan
full_name: Kopp, Stefan
last_name: Kopp
- first_name: Kirsten
full_name: Thommes, Kirsten
id: '72497'
last_name: Thommes
- first_name: Axel-Cyrille
full_name: Ngonga Ngomo, Axel-Cyrille
id: '65716'
last_name: Ngonga Ngomo
- first_name: Carsten
full_name: Schulte, Carsten
id: '60311'
last_name: Schulte
- first_name: Henning
full_name: Wachsmuth, Henning
id: '3900'
last_name: Wachsmuth
- first_name: Petra
full_name: Wagner, Petra
last_name: Wagner
- first_name: Britta
full_name: Wrede, Britta
last_name: Wrede
citation:
ama: 'Rohlfing KJ, Cimiano P, Scharlau I, et al. Explanation as a Social Practice:
Toward a Conceptual Framework for the Social Design of AI Systems. IEEE Transactions
on Cognitive and Developmental Systems. 2021;13(3):717-728. doi:10.1109/tcds.2020.3044366'
apa: 'Rohlfing, K. J., Cimiano, P., Scharlau, I., Matzner, T., Buhl, H. M., Buschmeier,
H., Esposito, E., Grimminger, A., Hammer, B., Haeb-Umbach, R., Horwath, I., Hüllermeier,
E., Kern, F., Kopp, S., Thommes, K., Ngonga Ngomo, A.-C., Schulte, C., Wachsmuth,
H., Wagner, P., & Wrede, B. (2021). Explanation as a Social Practice: Toward
a Conceptual Framework for the Social Design of AI Systems. IEEE Transactions
on Cognitive and Developmental Systems, 13(3), 717–728. https://doi.org/10.1109/tcds.2020.3044366'
bibtex: '@article{Rohlfing_Cimiano_Scharlau_Matzner_Buhl_Buschmeier_Esposito_Grimminger_Hammer_Haeb-Umbach_et
al._2021, title={Explanation as a Social Practice: Toward a Conceptual Framework
for the Social Design of AI Systems}, volume={13}, DOI={10.1109/tcds.2020.3044366},
number={3}, journal={IEEE Transactions on Cognitive and Developmental Systems},
author={Rohlfing, Katharina J. and Cimiano, Philipp and Scharlau, Ingrid and Matzner,
Tobias and Buhl, Heike M. and Buschmeier, Hendrik and Esposito, Elena and Grimminger,
Angela and Hammer, Barbara and Haeb-Umbach, Reinhold and et al.}, year={2021},
pages={717–728} }'
chicago: 'Rohlfing, Katharina J., Philipp Cimiano, Ingrid Scharlau, Tobias Matzner,
Heike M. Buhl, Hendrik Buschmeier, Elena Esposito, et al. “Explanation as a Social
Practice: Toward a Conceptual Framework for the Social Design of AI Systems.”
IEEE Transactions on Cognitive and Developmental Systems 13, no. 3 (2021):
717–28. https://doi.org/10.1109/tcds.2020.3044366.'
ieee: 'K. J. Rohlfing et al., “Explanation as a Social Practice: Toward a
Conceptual Framework for the Social Design of AI Systems,” IEEE Transactions
on Cognitive and Developmental Systems, vol. 13, no. 3, pp. 717–728, 2021,
doi: 10.1109/tcds.2020.3044366.'
mla: 'Rohlfing, Katharina J., et al. “Explanation as a Social Practice: Toward a
Conceptual Framework for the Social Design of AI Systems.” IEEE Transactions
on Cognitive and Developmental Systems, vol. 13, no. 3, 2021, pp. 717–28,
doi:10.1109/tcds.2020.3044366.'
short: K.J. Rohlfing, P. Cimiano, I. Scharlau, T. Matzner, H.M. Buhl, H. Buschmeier,
E. Esposito, A. Grimminger, B. Hammer, R. Haeb-Umbach, I. Horwath, E. Hüllermeier,
F. Kern, S. Kopp, K. Thommes, A.-C. Ngonga Ngomo, C. Schulte, H. Wachsmuth, P.
Wagner, B. Wrede, IEEE Transactions on Cognitive and Developmental Systems 13
(2021) 717–728.
date_created: 2021-09-14T20:52:57Z
date_updated: 2023-12-05T10:15:02Z
ddc:
- '300'
department:
- _id: '603'
- _id: '749'
- _id: '424'
- _id: '67'
- _id: '574'
- _id: '184'
- _id: '757'
- _id: '54'
- _id: '178'
doi: 10.1109/tcds.2020.3044366
file:
- access_level: open_access
content_type: application/pdf
creator: haebumb
date_created: 2023-11-20T16:33:51Z
date_updated: 2023-11-20T16:33:51Z
file_id: '49081'
file_name: 2020-12-01_explainability_final_version.pdf
file_size: 626217
relation: main_file
file_date_updated: 2023-11-20T16:33:51Z
has_accepted_license: '1'
intvolume: ' 13'
issue: '3'
keyword:
- Explainability
- process ofexplaining andunderstanding
- explainable artificial systems
language:
- iso: eng
oa: '1'
page: 717-728
project:
- _id: '109'
grant_number: '438445824'
name: 'TRR 318: TRR 318 - Erklärbarkeit konstruieren'
publication: IEEE Transactions on Cognitive and Developmental Systems
publication_identifier:
issn:
- 2379-8920
- 2379-8939
publication_status: published
quality_controlled: '1'
status: public
title: 'Explanation as a Social Practice: Toward a Conceptual Framework for the Social
Design of AI Systems'
type: journal_article
user_id: '42933'
volume: 13
year: '2021'
...
---
_id: '49487'
author:
- first_name: Natalia
full_name: Malancu, Natalia
last_name: Malancu
- first_name: Alexandra
full_name: Florea, Alexandra
id: '98958'
last_name: Florea
orcid: 0000-0003-0626-945X
citation:
ama: 'Malancu N, Florea A. Chapter 5: Quantitative methodological approaches to
citizenship and migration. In: Giugni M, Grasso M, eds. Handbook of Citizenship
and Migration. ; 2021. doi:https://doi.org/10.4337/9781789903133.00011'
apa: 'Malancu, N., & Florea, A. (2021). Chapter 5: Quantitative methodological
approaches to citizenship and migration. In M. Giugni & M. Grasso (Eds.),
Handbook of Citizenship and Migration. https://doi.org/10.4337/9781789903133.00011'
bibtex: '@inbook{Malancu_Florea_2021, title={Chapter 5: Quantitative methodological
approaches to citizenship and migration}, DOI={https://doi.org/10.4337/9781789903133.00011},
booktitle={Handbook of Citizenship and Migration}, author={Malancu, Natalia and
Florea, Alexandra}, editor={Giugni, Marco and Grasso, Maria}, year={2021} }'
chicago: 'Malancu, Natalia, and Alexandra Florea. “Chapter 5: Quantitative Methodological
Approaches to Citizenship and Migration.” In Handbook of Citizenship and Migration,
edited by Marco Giugni and Maria Grasso, 2021. https://doi.org/10.4337/9781789903133.00011.'
ieee: 'N. Malancu and A. Florea, “Chapter 5: Quantitative methodological approaches
to citizenship and migration,” in Handbook of Citizenship and Migration,
M. Giugni and M. Grasso, Eds. 2021.'
mla: 'Malancu, Natalia, and Alexandra Florea. “Chapter 5: Quantitative Methodological
Approaches to Citizenship and Migration.” Handbook of Citizenship and Migration,
edited by Marco Giugni and Maria Grasso, 2021, doi:https://doi.org/10.4337/9781789903133.00011.'
short: 'N. Malancu, A. Florea, in: M. Giugni, M. Grasso (Eds.), Handbook of Citizenship
and Migration, 2021.'
date_created: 2023-12-05T13:28:19Z
date_updated: 2023-12-05T13:38:08Z
department:
- _id: '603'
doi: https://doi.org/10.4337/9781789903133.00011
editor:
- first_name: Marco
full_name: Giugni, Marco
last_name: Giugni
- first_name: Maria
full_name: Grasso, Maria
last_name: Grasso
extern: '1'
language:
- iso: eng
publication: Handbook of Citizenship and Migration
publication_identifier:
unknown:
- 978 1 78990 312 6
status: public
title: 'Chapter 5: Quantitative methodological approaches to citizenship and migration'
type: book_chapter
user_id: '98958'
year: '2021'
...
---
_id: '48853'
abstract:
- lang: eng
text: In practise, it is often desirable to provide the decision-maker with a rich
set of diverse solutions of decent quality instead of just a single solution.
In this paper we study evolutionary diversity optimization for the knapsack problem
(KP). Our goal is to evolve a population of solutions that all have a profit of
at least (1 - {$ϵ$}) {$\cdot$} OPT, where OPT is the value of an optimal solution.
Furthermore, they should differ in structure with respect to an entropy-based
diversity measure. To this end we propose a simple ({$\mu$} + 1)-EA with initial
approximate solutions calculated by a well-known FPTAS for the KP. We investigate
the effect of different standard mutation operators and introduce biased mutation
and crossover which puts strong probability on flipping bits of low and/or high
frequency within the population. An experimental study on different instances
and settings shows that the proposed mutation operators in most cases perform
slightly inferior in the long term, but show strong benefits if the number of
function evaluations is severely limited.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Breeding Diverse Packings for the Knapsack
Problem by Means of Diversity-Tailored Evolutionary Algorithms. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO ’21. Association
for Computing Machinery; 2021:556–564. doi:10.1145/3449639.3459364'
apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.
Proceedings of the Genetic and Evolutionary Computation Conference, 556–564.
https://doi.org/10.1145/3449639.3459364
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
series={GECCO ’21}, title={Breeding Diverse Packings for the Knapsack Problem
by Means of Diversity-Tailored Evolutionary Algorithms}, DOI={10.1145/3449639.3459364},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Aneta and Neumann, Frank}, year={2021}, pages={556–564}, collection={GECCO ’21}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Breeding Diverse Packings
for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms.”
In Proceedings of the Genetic and Evolutionary Computation Conference,
556–564. GECCO ’21. New York, NY, USA: Association for Computing Machinery, 2021.
https://doi.org/10.1145/3449639.3459364.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Breeding Diverse Packings for the
Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 556–564,
doi: 10.1145/3449639.3459364.'
mla: Bossek, Jakob, et al. “Breeding Diverse Packings for the Knapsack Problem by
Means of Diversity-Tailored Evolutionary Algorithms.” Proceedings of the Genetic
and Evolutionary Computation Conference, Association for Computing Machinery,
2021, pp. 556–564, doi:10.1145/3449639.3459364.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2021, pp. 556–564.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:22Z
department:
- _id: '819'
doi: 10.1145/3449639.3459364
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- knapsack problem
- tailored operators
language:
- iso: eng
page: 556–564
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored
Evolutionary Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48855'
abstract:
- lang: eng
text: Computing sets of high quality solutions has gained increasing interest in
recent years. In this paper, we investigate how to obtain sets of optimal solutions
for the classical knapsack problem. We present an algorithm to count exactly the
number of optima to a zero-one knapsack problem instance. In addition, we show
how to efficiently sample uniformly at random from the set of all global optima.
In our experimental study, we investigate how the number of optima develops for
classical random benchmark instances dependent on their generator parameters.
We find that the number of global optima can increase exponentially for practically
relevant classes of instances with correlated weights and profits which poses
a justification for the considered exact counting problem.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for
the Knapsack Problem. In: Learning and Intelligent Optimization. Springer-Verlag;
2021:40–54. doi:10.1007/978-3-030-92121-7_4'
apa: Bossek, J., Neumann, A., & Neumann, F. (2021). Exact Counting and~Sampling
of Optima for the Knapsack Problem. Learning and Intelligent Optimization,
40–54. https://doi.org/10.1007/978-3-030-92121-7_4
bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg},
title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={10.1007/978-3-030-92121-7_4},
booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag},
author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54}
}'
chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling
of Optima for the Knapsack Problem.” In Learning and Intelligent Optimization,
40–54. Berlin, Heidelberg: Springer-Verlag, 2021. https://doi.org/10.1007/978-3-030-92121-7_4.'
ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima
for the Knapsack Problem,” in Learning and Intelligent Optimization, 2021,
pp. 40–54, doi: 10.1007/978-3-030-92121-7_4.'
mla: Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack
Problem.” Learning and Intelligent Optimization, Springer-Verlag, 2021,
pp. 40–54, doi:10.1007/978-3-030-92121-7_4.
short: 'J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization,
Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:14Z
department:
- _id: '819'
doi: 10.1007/978-3-030-92121-7_4
extern: '1'
keyword:
- Dynamic programming
- Exact counting
- Sampling
- Zero-one knapsack problem
language:
- iso: eng
page: 40–54
place: Berlin, Heidelberg
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-030-92120-0
publication_status: published
publisher: Springer-Verlag
status: public
title: Exact Counting and~Sampling of Optima for the Knapsack Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48860'
abstract:
- lang: eng
text: In the area of evolutionary computation the calculation of diverse sets of
high-quality solutions to a given optimization problem has gained momentum in
recent years under the term evolutionary diversity optimization. Theoretical insights
into the working principles of baseline evolutionary algorithms for diversity
optimization are still rare. In this paper we study the well-known Minimum Spanning
Tree problem (MST) in the context of diversity optimization where population diversity
is measured by the sum of pairwise edge overlaps. Theoretical results provide
insights into the fitness landscape of the MST diversity optimization problem
pointing out that even for a population of {$\mu$} = 2 fitness plateaus (of constant
length) can be reached, but nevertheless diverse sets can be calculated in polynomial
time. We supplement our theoretical results with a series of experiments for the
unconstrained and constraint case where all solutions need to fulfill a minimal
quality threshold. Our results show that a simple ({$\mu$} + 1)-EA can effectively
compute a diversified population of spanning trees of high quality.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Bossek J, Neumann F. Evolutionary Diversity Optimization and the Minimum Spanning
Tree Problem. In: Proceedings of the Genetic and Evolutionary Computation Conference.
GECCO ’21. Association for Computing Machinery; 2021:198–206. doi:10.1145/3449639.3459363'
apa: Bossek, J., & Neumann, F. (2021). Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem. Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. https://doi.org/10.1145/3449639.3459363
bibtex: '@inproceedings{Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO
’21}, title={Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem}, DOI={10.1145/3449639.3459363},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann,
Frank}, year={2021}, pages={198–206}, collection={GECCO ’21} }'
chicago: 'Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization
and the Minimum Spanning Tree Problem.” In Proceedings of the Genetic and Evolutionary
Computation Conference, 198–206. GECCO ’21. New York, NY, USA: Association
for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459363.'
ieee: 'J. Bossek and F. Neumann, “Evolutionary Diversity Optimization and the Minimum
Spanning Tree Problem,” in Proceedings of the Genetic and Evolutionary Computation
Conference, 2021, pp. 198–206, doi: 10.1145/3449639.3459363.'
mla: Bossek, Jakob, and Frank Neumann. “Evolutionary Diversity Optimization and
the Minimum Spanning Tree Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 198–206,
doi:10.1145/3449639.3459363.
short: 'J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation
Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp.
198–206.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:37Z
department:
- _id: '819'
doi: 10.1145/3449639.3459363
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimization
- minimum spanning tree
- runtime analysis
language:
- iso: eng
page: 198–206
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publication_status: published
publisher: Association for Computing Machinery
series_title: GECCO ’21
status: public
title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48862'
abstract:
- lang: eng
text: 'Most runtime analyses of randomised search heuristics focus on the expected
number of function evaluations to find a unique global optimum. We ask a fundamental
question: if additional search points are declared optimal, or declared as desirable
target points, do these additional optima speed up evolutionary algorithms? More
formally, we analyse the expected hitting time of a target set OPT {$\cup$} S
where S is a set of non-optimal search points and OPT is the set of optima and
compare it to the expected hitting time of OPT. We show that the answer to our
question depends on the number and placement of search points in S. For all black-box
algorithms and all fitness functions we show that, if additional optima are placed
randomly, even an exponential number of optima has a negligible effect on the
expected optimisation time. Considering Hamming balls around all global optima
gives an easier target for some algorithms and functions and can shift the phase
transition with respect to offspring population sizes in the (1,{$\lambda$}) EA
on One-Max. Finally, on functions where search trajectories typically join in
a single search point, turning one search point into an optimum drastically reduces
the expected optimisation time.'
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
citation:
ama: 'Bossek J, Sudholt D. Do Additional Optima Speed up Evolutionary Algorithms?
In: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms. Association for Computing Machinery; 2021:1–11.'
apa: Bossek, J., & Sudholt, D. (2021). Do Additional Optima Speed up Evolutionary
Algorithms? In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms (pp. 1–11). Association for Computing Machinery.
bibtex: '@inbook{Bossek_Sudholt_2021, place={New York, NY, USA}, title={Do Additional
Optima Speed up Evolutionary Algorithms?}, booktitle={Proceedings of the 16th
ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association
for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2021},
pages={1–11} }'
chicago: 'Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
Algorithms?” In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 1–11. New York, NY, USA: Association for Computing
Machinery, 2021.'
ieee: 'J. Bossek and D. Sudholt, “Do Additional Optima Speed up Evolutionary Algorithms?,”
in Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms, New York, NY, USA: Association for Computing Machinery, 2021,
pp. 1–11.'
mla: Bossek, Jakob, and Dirk Sudholt. “Do Additional Optima Speed up Evolutionary
Algorithms?” Proceedings of the 16th ACM/SIGEVO Conference on Foundations of
Genetic Algorithms, Association for Computing Machinery, 2021, pp. 1–11.
short: 'J. Bossek, D. Sudholt, in: Proceedings of the 16th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms, Association for Computing Machinery, New
York, NY, USA, 2021, pp. 1–11.'
date_created: 2023-11-14T15:58:55Z
date_updated: 2023-12-13T10:45:31Z
department:
- _id: '819'
extern: '1'
keyword:
- evolutionary algorithms
- pseudo-boolean functions
- runtime analysis
- theory
language:
- iso: eng
page: 1–11
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publication_status: published
publisher: Association for Computing Machinery
status: public
title: Do Additional Optima Speed up Evolutionary Algorithms?
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48881'
abstract:
- lang: eng
text: 'Classic automated algorithm selection (AS) for (combinatorial) optimization
problems heavily relies on so-called instance features, i.e., numerical characteristics
of the problem at hand ideally extracted with computationally low-demanding routines.
For the traveling salesperson problem (TSP) a plethora of features have been suggested.
Most of these features are, if at all, only normalized imprecisely raising the
issue of feature values being strongly affected by the instance size. Such artifacts
may have detrimental effects on algorithm selection models. We propose a normalization
for two feature groups which stood out in multiple AS studies on the TSP: (a)
features based on a minimum spanning tree (MST) and (b) a k-nearest neighbor graph
(NNG) transformation of the input instance. To this end we theoretically derive
minimum and maximum values for properties of MSTs and k-NNGs of Euclidean graphs.
We analyze the differences in feature space between normalized versions of these
features and their unnormalized counterparts. Our empirical investigations on
various TSP benchmark sets point out that the feature scaling succeeds in eliminating
the effect of the instance size. Eventually, a proof-of-concept AS-study shows
promising results: models trained with normalized features tend to outperform
those trained with the respective vanilla features.'
author:
- first_name: Jonathan
full_name: Heins, Jonathan
last_name: Heins
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Janina
full_name: Pohl, Janina
last_name: Pohl
- first_name: Moritz
full_name: Seiler, Moritz
last_name: Seiler
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
citation:
ama: 'Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. On the Potential
of Normalized TSP Features for Automated Algorithm Selection. In: Proceedings
of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–15.'
apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., & Kerschke,
P. (2021). On the Potential of Normalized TSP Features for Automated Algorithm
Selection. In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms (pp. 1–15). Association for Computing Machinery.
bibtex: '@inbook{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2021, place={New York,
NY, USA}, title={On the Potential of Normalized TSP Features for Automated Algorithm
Selection}, booktitle={Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Heins,
Jonathan and Bossek, Jakob and Pohl, Janina and Seiler, Moritz and Trautmann,
Heike and Kerschke, Pascal}, year={2021}, pages={1–15} }'
chicago: 'Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann,
and Pascal Kerschke. “On the Potential of Normalized TSP Features for Automated
Algorithm Selection.” In Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, 1–15. New York, NY, USA: Association for Computing
Machinery, 2021.'
ieee: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “On
the Potential of Normalized TSP Features for Automated Algorithm Selection,” in
Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–15.'
mla: Heins, Jonathan, et al. “On the Potential of Normalized TSP Features for Automated
Algorithm Selection.” Proceedings of the 16th ACM/SIGEVO Conference on Foundations
of Genetic Algorithms, Association for Computing Machinery, 2021, pp. 1–15.
short: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, in:
Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms,
Association for Computing Machinery, New York, NY, USA, 2021, pp. 1–15.'
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:47:23Z
department:
- _id: '819'
extern: '1'
keyword:
- automated algorithm selection
- graph theory
- instance features
- normalization
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–15
place: New York, NY, USA
publication: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: On the Potential of Normalized TSP Features for Automated Algorithm Selection
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48876'
abstract:
- lang: eng
text: In recent years, Evolutionary Algorithms (EAs) have frequently been adopted
to evolve instances for optimization problems that pose difficulties for one algorithm
while being rather easy for a competitor and vice versa. Typically, this is achieved
by either minimizing or maximizing the performance difference or ratio which serves
as the fitness function. Repeating this process is useful to gain insights into
strengths/weaknesses of certain algorithms or to build a set of instances with
strong performance differences as a foundation for automatic per-instance algorithm
selection or configuration. We contribute to this branch of research by proposing
fitness-functions to evolve instances that show large performance differences
for more than just two algorithms simultaneously. As a proof-of-principle, we
evolve instances of the multi-component Traveling Thief Problem (TTP) for three
incomplete TTP-solvers. Our results point out that our strategies are promising,
but unsurprisingly their success strongly relies on the algorithms’ performance
complementarity.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Markus
full_name: Wagner, Markus
last_name: Wagner
citation:
ama: 'Bossek J, Wagner M. Generating Instances with Performance Differences for
More than Just Two Algorithms. In: Proceedings of the Genetic and Evolutionary
Computation Conference Companion. GECCO’21. Association for Computing Machinery;
2021:1423–1432. doi:10.1145/3449726.3463165'
apa: Bossek, J., & Wagner, M. (2021). Generating Instances with Performance
Differences for More than Just Two Algorithms. Proceedings of the Genetic and
Evolutionary Computation Conference Companion, 1423–1432. https://doi.org/10.1145/3449726.3463165
bibtex: '@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21},
title={Generating Instances with Performance Differences for More than Just Two
Algorithms}, DOI={10.1145/3449726.3463165},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob
and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }'
chicago: 'Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance
Differences for More than Just Two Algorithms.” In Proceedings of the Genetic
and Evolutionary Computation Conference Companion, 1423–1432. GECCO’21. New
York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449726.3463165.'
ieee: 'J. Bossek and M. Wagner, “Generating Instances with Performance Differences
for More than Just Two Algorithms,” in Proceedings of the Genetic and Evolutionary
Computation Conference Companion, 2021, pp. 1423–1432, doi: 10.1145/3449726.3463165.'
mla: Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences
for More than Just Two Algorithms.” Proceedings of the Genetic and Evolutionary
Computation Conference Companion, Association for Computing Machinery, 2021,
pp. 1423–1432, doi:10.1145/3449726.3463165.
short: 'J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation
Conference Companion, Association for Computing Machinery, New York, NY, USA,
2021, pp. 1423–1432.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:41Z
department:
- _id: '819'
doi: 10.1145/3449726.3463165
extern: '1'
keyword:
- evolutionary algorithms
- evolving instances
- fitness function
- instance hardness
- traveling thief problem (TTP)
language:
- iso: eng
page: 1423–1432
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion
publication_identifier:
isbn:
- 978-1-4503-8351-6
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Generating Instances with Performance Differences for More than Just Two Algorithms
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48893'
abstract:
- lang: eng
text: Computing diverse sets of high-quality solutions has gained increasing attention
among the evolutionary computation community in recent years. It allows practitioners
to choose from a set of high-quality alternatives. In this paper, we employ a
population diversity measure, called the high-order entropy measure, in an evolutionary
algorithm to compute a diverse set of high-quality solutions for the Traveling
Salesperson Problem. In contrast to previous studies, our approach allows diversifying
segments of tours containing several edges based on the entropy measure. We examine
the resulting evolutionary diversity optimisation approach precisely in terms
of the final set of solutions and theoretical properties. Experimental results
show significant improvements compared to a recently proposed edge-based diversity
optimisation approach when working with a large population of solutions or long
segments.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Entropy-Based Evolutionary Diversity
Optimisation for the Traveling Salesperson Problem. In: Proceedings of the
Genetic and Evolutionary Computation Conference. GECCO’21. Association for
Computing Machinery; 2021:600–608. doi:10.1145/3449639.3459384'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem. Proceedings
of the Genetic and Evolutionary Computation Conference, 600–608. https://doi.org/10.1145/3449639.3459384
bibtex: '@inproceedings{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York,
NY, USA}, series={GECCO’21}, title={Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem}, DOI={10.1145/3449639.3459384},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Nikfarjam, Adel and Bossek,
Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={600–608}, collection={GECCO’21}
}'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Entropy-Based
Evolutionary Diversity Optimisation for the Traveling Salesperson Problem.” In
Proceedings of the Genetic and Evolutionary Computation Conference, 600–608.
GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459384.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Entropy-Based Evolutionary
Diversity Optimisation for the Traveling Salesperson Problem,” in Proceedings
of the Genetic and Evolutionary Computation Conference, 2021, pp. 600–608,
doi: 10.1145/3449639.3459384.'
mla: Nikfarjam, Adel, et al. “Entropy-Based Evolutionary Diversity Optimisation
for the Traveling Salesperson Problem.” Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, 2021, pp. 600–608,
doi:10.1145/3449639.3459384.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
Genetic and Evolutionary Computation Conference, Association for Computing Machinery,
New York, NY, USA, 2021, pp. 600–608.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:50:06Z
department:
- _id: '819'
doi: 10.1145/3449639.3459384
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimisation
- high-order entropy
- traveling salesperson problem
language:
- iso: eng
page: 600–608
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson
Problem
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48891'
abstract:
- lang: eng
text: Submodular functions allow to model many real-world optimisation problems.
This paper introduces approaches for computing diverse sets of high quality solutions
for submodular optimisation problems with uniform and knapsack constraints. We
first present diversifying greedy sampling approaches and analyse them with respect
to the diversity measured by entropy and the approximation quality of the obtained
solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO)
approach to further improve diversity of the set of solutions. We carry out experimental
investigations on popular submodular benchmark problems and analyse trade-offs
in terms of solution quality and diversity of the resulting solution sets.
author:
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Neumann A, Bossek J, Neumann F. Diversifying Greedy Sampling and Evolutionary
Diversity Optimisation for Constrained Monotone Submodular Functions. In: Proceedings
of the Genetic and Evolutionary Computation Conference. GECCO’21. Association
for Computing Machinery; 2021:261–269. doi:10.1145/3449639.3459385'
apa: Neumann, A., Bossek, J., & Neumann, F. (2021). Diversifying Greedy Sampling
and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.
Proceedings of the Genetic and Evolutionary Computation Conference, 261–269.
https://doi.org/10.1145/3449639.3459385
bibtex: '@inproceedings{Neumann_Bossek_Neumann_2021, place={New York, NY, USA},
series={GECCO’21}, title={Diversifying Greedy Sampling and Evolutionary Diversity
Optimisation for Constrained Monotone Submodular Functions}, DOI={10.1145/3449639.3459385},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
publisher={Association for Computing Machinery}, author={Neumann, Aneta and Bossek,
Jakob and Neumann, Frank}, year={2021}, pages={261–269}, collection={GECCO’21}
}'
chicago: 'Neumann, Aneta, Jakob Bossek, and Frank Neumann. “Diversifying Greedy
Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular
Functions.” In Proceedings of the Genetic and Evolutionary Computation Conference,
261–269. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021.
https://doi.org/10.1145/3449639.3459385.'
ieee: 'A. Neumann, J. Bossek, and F. Neumann, “Diversifying Greedy Sampling and
Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions,”
in Proceedings of the Genetic and Evolutionary Computation Conference,
2021, pp. 261–269, doi: 10.1145/3449639.3459385.'
mla: Neumann, Aneta, et al. “Diversifying Greedy Sampling and Evolutionary Diversity
Optimisation for Constrained Monotone Submodular Functions.” Proceedings of
the Genetic and Evolutionary Computation Conference, Association for Computing
Machinery, 2021, pp. 261–269, doi:10.1145/3449639.3459385.
short: 'A. Neumann, J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary
Computation Conference, Association for Computing Machinery, New York, NY, USA,
2021, pp. 261–269.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:49:25Z
department:
- _id: '819'
doi: 10.1145/3449639.3459385
extern: '1'
keyword:
- evolutionary algorithms
- evolutionary diversity optimisation
- sub-modular functions
language:
- iso: eng
page: 261–269
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference
publication_identifier:
isbn:
- 978-1-4503-8350-9
publisher: Association for Computing Machinery
series_title: GECCO’21
status: public
title: Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained
Monotone Submodular Functions
type: conference
user_id: '102979'
year: '2021'
...
---
_id: '48892'
abstract:
- lang: eng
text: Evolutionary algorithms based on edge assembly crossover (EAX) constitute
some of the best performing incomplete solvers for the well-known traveling salesperson
problem (TSP). Often, it is desirable to compute not just a single solution for
a given problem, but a diverse set of high quality solutions from which a decision
maker can choose one for implementation. Currently, there are only a few approaches
for computing a diverse solution set for the TSP. Furthermore, almost all of them
assume that the optimal solution is known. In this paper, we introduce evolutionary
diversity optimisation (EDO) approaches for the TSP that find a diverse set of
tours when the optimal tour is known or unknown. We show how to adopt EAX to not
only find a high-quality solution but also to maximise the diversity of the population.
The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse
high-quality tours when the optimal solution for the TSP is known or unknown.
A comparison to existing approaches shows that they are clearly outperformed by
EAX-EDO.
author:
- first_name: Adel
full_name: Nikfarjam, Adel
last_name: Nikfarjam
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Aneta
full_name: Neumann, Aneta
last_name: Neumann
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
citation:
ama: 'Nikfarjam A, Bossek J, Neumann A, Neumann F. Computing Diverse Sets of High
Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation. In: Proceedings
of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms. Association
for Computing Machinery; 2021:1–11.'
apa: Nikfarjam, A., Bossek, J., Neumann, A., & Neumann, F. (2021). Computing
Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation.
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms (pp. 1–11). Association for Computing Machinery.
bibtex: '@inbook{Nikfarjam_Bossek_Neumann_Neumann_2021, place={New York, NY, USA},
title={Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation}, booktitle={Proceedings of the 16th ACM}/SIGEVO Conference
on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery},
author={Nikfarjam, Adel and Bossek, Jakob and Neumann, Aneta and Neumann, Frank},
year={2021}, pages={1–11} }'
chicago: 'Nikfarjam, Adel, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Computing
Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation.”
In Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms, 1–11. New York, NY, USA: Association for Computing Machinery,
2021.'
ieee: 'A. Nikfarjam, J. Bossek, A. Neumann, and F. Neumann, “Computing Diverse Sets
of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation,” in
Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms,
New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–11.'
mla: Nikfarjam, Adel, et al. “Computing Diverse Sets of High Quality TSP Tours by
EAX-Based Evolutionary Diversity Optimisation.” Proceedings of the 16th ACM}/SIGEVO
Conference on Foundations of Genetic Algorithms, Association for Computing
Machinery, 2021, pp. 1–11.
short: 'A. Nikfarjam, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the
16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms, Association
for Computing Machinery, New York, NY, USA, 2021, pp. 1–11.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:59Z
department:
- _id: '819'
extern: '1'
keyword:
- edge assembly crossover (EAX)
- evolutionary algorithms
- evolutionary diversity optimisation (EDO)
- traveling salesperson problem (TSP)
language:
- iso: eng
page: 1–11
place: New York, NY, USA
publication: Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-1-4503-8352-3
publisher: Association for Computing Machinery
status: public
title: Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary
Diversity Optimisation
type: book_chapter
user_id: '102979'
year: '2021'
...
---
_id: '48854'
abstract:
- lang: eng
text: We contribute to the theoretical understanding of randomized search heuristics
for dynamic problems. We consider the classical vertex coloring problem on graphs
and investigate the dynamic setting where edges are added to the current graph.
We then analyze the expected time for randomized search heuristics to recompute
high quality solutions. The (1+1) Evolutionary Algorithm and RLS operate in a
setting where the number of colors is bounded and we are minimizing the number
of conflicts. Iterated local search algorithms use an unbounded color palette
and aim to use the smallest colors and, consequently, the smallest number of colors.
We identify classes of bipartite graphs where reoptimization is as hard as or
even harder than optimization from scratch, i.e., starting with a random initialization.
Even adding a single edge can lead to hard symmetry problems. However, graph classes
that are hard for one algorithm turn out to be easy for others. In most cases
our bounds show that reoptimization is faster than optimizing from scratch. We
further show that tailoring mutation operators to parts of the graph where changes
have occurred can significantly reduce the expected reoptimization time. In most
settings the expected reoptimization time for such tailored algorithms is linear
in the number of added edges. However, tailored algorithms cannot prevent exponential
times in settings where the original algorithm is inefficient.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Frank
full_name: Neumann, Frank
last_name: Neumann
- first_name: Pan
full_name: Peng, Pan
last_name: Peng
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
citation:
ama: Bossek J, Neumann F, Peng P, Sudholt D. Time Complexity Analysis of Randomized
Search Heuristics for the Dynamic Graph Coloring Problem. Algorithmica.
2021;83(10):3148–3179. doi:10.1007/s00453-021-00838-3
apa: Bossek, J., Neumann, F., Peng, P., & Sudholt, D. (2021). Time Complexity
Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.
Algorithmica, 83(10), 3148–3179. https://doi.org/10.1007/s00453-021-00838-3
bibtex: '@article{Bossek_Neumann_Peng_Sudholt_2021, title={Time Complexity Analysis
of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}, volume={83},
DOI={10.1007/s00453-021-00838-3},
number={10}, journal={Algorithmica}, author={Bossek, Jakob and Neumann, Frank
and Peng, Pan and Sudholt, Dirk}, year={2021}, pages={3148–3179} }'
chicago: 'Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “Time Complexity
Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.”
Algorithmica 83, no. 10 (2021): 3148–3179. https://doi.org/10.1007/s00453-021-00838-3.'
ieee: 'J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “Time Complexity Analysis
of Randomized Search Heuristics for the Dynamic Graph Coloring Problem,” Algorithmica,
vol. 83, no. 10, pp. 3148–3179, 2021, doi: 10.1007/s00453-021-00838-3.'
mla: Bossek, Jakob, et al. “Time Complexity Analysis of Randomized Search Heuristics
for the Dynamic Graph Coloring Problem.” Algorithmica, vol. 83, no. 10,
2021, pp. 3148–3179, doi:10.1007/s00453-021-00838-3.
short: J. Bossek, F. Neumann, P. Peng, D. Sudholt, Algorithmica 83 (2021) 3148–3179.
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:51:34Z
department:
- _id: '819'
doi: 10.1007/s00453-021-00838-3
intvolume: ' 83'
issue: '10'
keyword:
- Dynamic optimization
- Evolutionary algorithms
- Running time analysis
language:
- iso: eng
page: 3148–3179
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
status: public
title: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph
Coloring Problem
type: journal_article
user_id: '102979'
volume: 83
year: '2021'
...