---
_id: '56298'
abstract:
- lang: eng
text: "In the general pattern formation (GPF) problem, a swarm of simple autonomous,\r\ndisoriented
robots must form a given pattern. The robots' simplicity imply a\r\nstrong limitation:
When the initial configuration is rotationally symmetric,\r\nonly patterns with
a similar symmetry can be formed [Yamashita, Suzyuki; TCS\r\n2010]. The only known
algorithm to form large patterns with limited visibility\r\nand without memory
requires the robots to start in a near-gathering (a swarm of\r\nconstant diameter)
[Hahn et al.; SAND 2024]. However, not only do we not know\r\nany near-gathering
algorithm guaranteed to preserve symmetry but most natural\r\ngathering strategies
trivially increase symmetries [Castenow et al.; OPODIS\r\n2022].\r\n Thus, we
study near-gathering without changing the swarm's rotational\r\nsymmetry for disoriented,
oblivious robots with limited visibility (the\r\nOBLOT-model, see [Flocchini et
al.; 2019]). We introduce a technique based on\r\nthe theory of dynamical systems
to analyze how a given algorithm affects\r\nsymmetry and provide sufficient conditions
for symmetry preservation. Until\r\nnow, it was unknown whether the considered
OBLOT-model allows for any\r\nnon-trivial algorithm that always preserves symmetry.
Our first result shows\r\nthat a variant of Go-to-the-Average always preserves
symmetry but may sometimes\r\nlead to multiple, unconnected near-gathering clusters.
Our second result is a\r\nsymmetry-preserving near-gathering algorithm that works
on swarms with a convex\r\nboundary (the outer boundary of the unit disc graph)
and without holes (circles\r\nof diameter 1 inside the boundary without any robots)."
author:
- first_name: Raphael
full_name: Gerlach, Raphael
id: '32655'
last_name: Gerlach
orcid: 0009-0002-4750-2051
- first_name: Sören
full_name: von der Gracht, Sören
id: '97359'
last_name: von der Gracht
orcid: 0000-0002-8054-2058
- first_name: Christopher
full_name: Hahn, Christopher
last_name: Hahn
- first_name: Jonas
full_name: Harbig, Jonas
id: '47213'
last_name: Harbig
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
citation:
ama: 'Gerlach R, von der Gracht S, Hahn C, Harbig J, Kling P. Symmetry Preservation
in Swarms of Oblivious Robots with Limited Visibility. In: Bonomi S, Galletta
L, Rivière Etienne, Schiavoni Valerio, eds. 28th International Conference
on Principles of Distributed Systems (OPODIS 2024). Vol 324. Leibniz International
Proceedings in Informatics (LIPIcs). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.OPODIS.2024.13'
apa: Gerlach, R., von der Gracht, S., Hahn, C., Harbig, J., & Kling, P. (2025).
Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility.
In S. Bonomi, L. Galletta, Etienne Rivière, & Valerio Schiavoni (Eds.),
28th International Conference on Principles of Distributed Systems (OPODIS
2024) (Vol. 324). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2024.13
bibtex: '@inproceedings{Gerlach_von der Gracht_Hahn_Harbig_Kling_2025, series={Leibniz
International Proceedings in Informatics (LIPIcs)}, title={Symmetry Preservation
in Swarms of Oblivious Robots with Limited Visibility}, volume={324}, DOI={10.4230/LIPIcs.OPODIS.2024.13},
booktitle={28th International Conference on Principles of Distributed Systems
(OPODIS 2024)}, publisher={Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
author={Gerlach, Raphael and von der Gracht, Sören and Hahn, Christopher and Harbig,
Jonas and Kling, Peter}, editor={Bonomi, Silvia and Galletta, Letterio and Rivière, Etienne
and Schiavoni, Valerio}, year={2025}, collection={Leibniz International Proceedings
in Informatics (LIPIcs)} }'
chicago: Gerlach, Raphael, Sören von der Gracht, Christopher Hahn, Jonas Harbig,
and Peter Kling. “Symmetry Preservation in Swarms of Oblivious Robots with Limited
Visibility.” In 28th International Conference on Principles of Distributed
Systems (OPODIS 2024), edited by Silvia Bonomi, Letterio Galletta, Etienne
Rivière, and Valerio Schiavoni, Vol. 324. Leibniz International Proceedings in
Informatics (LIPIcs). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2025.
https://doi.org/10.4230/LIPIcs.OPODIS.2024.13.
ieee: 'R. Gerlach, S. von der Gracht, C. Hahn, J. Harbig, and P. Kling, “Symmetry
Preservation in Swarms of Oblivious Robots with Limited Visibility,” in 28th
International Conference on Principles of Distributed Systems (OPODIS 2024),
Lucca, Italy, 2025, vol. 324, doi: 10.4230/LIPIcs.OPODIS.2024.13.'
mla: Gerlach, Raphael, et al. “Symmetry Preservation in Swarms of Oblivious Robots
with Limited Visibility.” 28th International Conference on Principles of Distributed
Systems (OPODIS 2024), edited by Silvia Bonomi et al., vol. 324, Schloss Dagstuhl
-- Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.OPODIS.2024.13.
short: 'R. Gerlach, S. von der Gracht, C. Hahn, J. Harbig, P. Kling, in: S. Bonomi,
L. Galletta, Etienne Rivière, Valerio Schiavoni (Eds.), 28th International Conference
on Principles of Distributed Systems (OPODIS 2024), Schloss Dagstuhl -- Leibniz-Zentrum
für Informatik, 2025.'
conference:
end_date: 2024-12-13
location: Lucca, Italy
name: 28th International Conference on Principles of Distributed Systems (OPODIS
2024)
start_date: 2024-12-11
date_created: 2024-10-01T13:29:43Z
date_updated: 2025-01-09T11:39:19Z
department:
- _id: '101'
doi: 10.4230/LIPIcs.OPODIS.2024.13
editor:
- first_name: Silvia
full_name: Bonomi, Silvia
last_name: Bonomi
- first_name: Letterio
full_name: Galletta, Letterio
last_name: Galletta
- first_name: ' Etienne'
full_name: Rivière, Etienne
last_name: Rivière
- first_name: ' Valerio'
full_name: Schiavoni, Valerio
last_name: Schiavoni
external_id:
arxiv:
- '2409.19277'
intvolume: ' 324'
keyword:
- Swarm Algorithm
- Swarm Robots
- Distributed Algorithm
- Pattern Formation
- Limited Visibility
- Oblivious
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2409.19277
oa: '1'
project:
- _id: '106'
grant_number: '453112019'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: 28th International Conference on Principles of Distributed Systems (OPODIS
2024)
publication_identifier:
isbn:
- 978-3-95977-360-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility
type: conference
user_id: '97359'
volume: 324
year: '2025'
...
---
_id: '61339'
author:
- first_name: Marius
full_name: Protte, Marius
id: '44549'
last_name: Protte
- first_name: Behnud Mir
full_name: Djawadi, Behnud Mir
last_name: Djawadi
citation:
ama: 'Protte M, Djawadi BM. Human vs. Algorithmic Auditors: The Impact of Entity
Type and Ambiguity on Human Dishonesty. Frontiers in Behavioral Economics.
2025;4:1645749. doi:10.3389/frbhe.2025.1645749'
apa: 'Protte, M., & Djawadi, B. M. (2025). Human vs. Algorithmic Auditors: The
Impact of Entity Type and Ambiguity on Human Dishonesty. Frontiers in Behavioral
Economics, 4, 1645749. https://doi.org/10.3389/frbhe.2025.1645749'
bibtex: '@article{Protte_Djawadi_2025, title={Human vs. Algorithmic Auditors: The
Impact of Entity Type and Ambiguity on Human Dishonesty}, volume={4}, DOI={10.3389/frbhe.2025.1645749},
journal={Frontiers in Behavioral Economics}, author={Protte, Marius and Djawadi,
Behnud Mir}, year={2025}, pages={1645749} }'
chicago: 'Protte, Marius, and Behnud Mir Djawadi. “Human vs. Algorithmic Auditors:
The Impact of Entity Type and Ambiguity on Human Dishonesty.” Frontiers in
Behavioral Economics 4 (2025): 1645749. https://doi.org/10.3389/frbhe.2025.1645749.'
ieee: 'M. Protte and B. M. Djawadi, “Human vs. Algorithmic Auditors: The Impact
of Entity Type and Ambiguity on Human Dishonesty,” Frontiers in Behavioral
Economics, vol. 4, p. 1645749, 2025, doi: 10.3389/frbhe.2025.1645749.'
mla: 'Protte, Marius, and Behnud Mir Djawadi. “Human vs. Algorithmic Auditors: The
Impact of Entity Type and Ambiguity on Human Dishonesty.” Frontiers in Behavioral
Economics, vol. 4, 2025, p. 1645749, doi:10.3389/frbhe.2025.1645749.'
short: M. Protte, B.M. Djawadi, Frontiers in Behavioral Economics 4 (2025) 1645749.
date_created: 2025-09-18T07:52:40Z
date_updated: 2025-09-29T09:31:38Z
doi: 10.3389/frbhe.2025.1645749
intvolume: ' 4'
keyword:
- cheating
- human-machine interaction
- ambiguity
- verification process
- algorithm aversion
- algorithm appreciation
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.frontiersin.org/journals/behavioral-economics/articles/10.3389/frbhe.2025.1645749/full
oa: '1'
page: '1645749'
publication: Frontiers in Behavioral Economics
status: public
title: 'Human vs. Algorithmic Auditors: The Impact of Entity Type and Ambiguity on
Human Dishonesty'
type: journal_article
user_id: '44549'
volume: 4
year: '2025'
...
---
_id: '54548'
author:
- first_name: Raphael Patrick
full_name: Prager, Raphael Patrick
last_name: Prager
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: Prager RP, Trautmann H. Exploratory Landscape Analysis for Mixed-Variable Problems.
IEEE Transactions on Evolutionary Computation. Published online 2024:1-1.
doi:10.1109/TEVC.2024.3399560
apa: Prager, R. P., & Trautmann, H. (2024). Exploratory Landscape Analysis for
Mixed-Variable Problems. IEEE Transactions on Evolutionary Computation,
1–1. https://doi.org/10.1109/TEVC.2024.3399560
bibtex: '@article{Prager_Trautmann_2024, title={Exploratory Landscape Analysis for
Mixed-Variable Problems}, DOI={10.1109/TEVC.2024.3399560},
journal={IEEE Transactions on Evolutionary Computation}, author={Prager, Raphael
Patrick and Trautmann, Heike}, year={2024}, pages={1–1} }'
chicago: Prager, Raphael Patrick, and Heike Trautmann. “Exploratory Landscape Analysis
for Mixed-Variable Problems.” IEEE Transactions on Evolutionary Computation,
2024, 1–1. https://doi.org/10.1109/TEVC.2024.3399560.
ieee: 'R. P. Prager and H. Trautmann, “Exploratory Landscape Analysis for Mixed-Variable
Problems,” IEEE Transactions on Evolutionary Computation, pp. 1–1, 2024,
doi: 10.1109/TEVC.2024.3399560.'
mla: Prager, Raphael Patrick, and Heike Trautmann. “Exploratory Landscape Analysis
for Mixed-Variable Problems.” IEEE Transactions on Evolutionary Computation,
2024, pp. 1–1, doi:10.1109/TEVC.2024.3399560.
short: R.P. Prager, H. Trautmann, IEEE Transactions on Evolutionary Computation
(2024) 1–1.
date_created: 2024-06-03T06:16:33Z
date_updated: 2024-06-03T06:17:13Z
department:
- _id: '819'
doi: 10.1109/TEVC.2024.3399560
keyword:
- Optimization
- Evolutionary computation
- Benchmark testing
- Hyperparameter optimization
- Portfolios
- Extraterrestrial measurements
- Dispersion
- Exploratory landscape analysis
- mixed-variable problem
- mixed search spaces
- automated algorithm selection
language:
- iso: eng
page: 1-1
publication: IEEE Transactions on Evolutionary Computation
status: public
title: Exploratory Landscape Analysis for Mixed-Variable Problems
type: journal_article
user_id: '15504'
year: '2024'
...
---
_id: '37312'
abstract:
- lang: eng
text: Optimal decision making requires appropriate evaluation of advice. Recent
literature reports that algorithm aversion reduces the effectiveness of predictive
algorithms. However, it remains unclear how people recover from bad advice given
by an otherwise good advisor. Previous work has focused on algorithm aversion
at a single time point. We extend this work by examining successive decisions
in a time series forecasting task using an online between-subjects experiment
(N = 87). Our empirical results do not confirm algorithm aversion immediately
after bad advice. The estimated effect suggests an increasing algorithm appreciation
over time. Our work extends the current knowledge on algorithm aversion with insights
into how weight on advice is adjusted over consecutive tasks. Since most forecasting
tasks are not one-off decisions, this also has implications for practitioners.
author:
- first_name: Dirk
full_name: Leffrang, Dirk
id: '51271'
last_name: Leffrang
orcid: 0000-0001-9004-2391
- first_name: Kevin
full_name: Bösch, Kevin
last_name: Bösch
- first_name: Oliver
full_name: Müller, Oliver
id: '72849'
last_name: Müller
citation:
ama: 'Leffrang D, Bösch K, Müller O. Do People Recover from Algorithm Aversion?
An Experimental Study of Algorithm Aversion over Time. In: Hawaii International
Conference on System Sciences. ; 2023.'
apa: Leffrang, D., Bösch, K., & Müller, O. (2023). Do People Recover from Algorithm
Aversion? An Experimental Study of Algorithm Aversion over Time. Hawaii International
Conference on System Sciences. Hawaii International Conference on System Sciences.
bibtex: '@inproceedings{Leffrang_Bösch_Müller_2023, title={Do People Recover from
Algorithm Aversion? An Experimental Study of Algorithm Aversion over Time}, booktitle={Hawaii
International Conference on System Sciences}, author={Leffrang, Dirk and Bösch,
Kevin and Müller, Oliver}, year={2023} }'
chicago: Leffrang, Dirk, Kevin Bösch, and Oliver Müller. “Do People Recover from
Algorithm Aversion? An Experimental Study of Algorithm Aversion over Time.” In
Hawaii International Conference on System Sciences, 2023.
ieee: D. Leffrang, K. Bösch, and O. Müller, “Do People Recover from Algorithm Aversion?
An Experimental Study of Algorithm Aversion over Time,” presented at the Hawaii
International Conference on System Sciences, 2023.
mla: Leffrang, Dirk, et al. “Do People Recover from Algorithm Aversion? An Experimental
Study of Algorithm Aversion over Time.” Hawaii International Conference on
System Sciences, 2023.
short: 'D. Leffrang, K. Bösch, O. Müller, in: Hawaii International Conference on
System Sciences, 2023.'
conference:
name: Hawaii International Conference on System Sciences
date_created: 2023-01-18T10:53:51Z
date_updated: 2024-01-10T09:52:59Z
department:
- _id: '196'
keyword:
- Algorithm aversion
- Time series
- Decision making
- Advice taking
- Forecasting
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://scholarspace.manoa.hawaii.edu/items/62b58ddc-895c-48c3-8194-522a1758a26f
oa: '1'
publication: Hawaii International Conference on System Sciences
status: public
title: Do People Recover from Algorithm Aversion? An Experimental Study of Algorithm
Aversion over Time
type: conference
user_id: '51271'
year: '2023'
...
---
_id: '50121'
abstract:
- lang: eng
text: Many researchers and practitioners see artificial intelligence as a game changer
compared to classical statistical models. However, some software providers engage
in “AI washing”, relabeling solutions that use simple statistical models as AI
systems. By contrast, research on algorithm aversion unsystematically varied the
labels for advisors and treated labels such as "artificial intelligence" and "statistical
model" synonymously. This study investigates the effect of individual labels on
users' actual advice utilization behavior. Through two incentivized online within-subjects
experiments on regression tasks, we find that labeling human advisors with labels
that suggest higher expertise leads to an increase in advice-taking, even though
the content of the advice remains the same. In contrast, our results do not suggest
such an expert effect for advice-taking from algorithms, despite differences in
self-reported perception. These findings challenge the effectiveness of framing
intelligent systems as AI-based systems and have important implications for both
research and practice.
author:
- first_name: Dirk
full_name: Leffrang, Dirk
id: '51271'
last_name: Leffrang
orcid: 0000-0001-9004-2391
citation:
ama: 'Leffrang D. AI Washing: The Framing Effect of Labels on Algorithmic Advice
Utilization. In: International Conference on Information Systems. ; 2023.'
apa: 'Leffrang, D. (2023). AI Washing: The Framing Effect of Labels on Algorithmic
Advice Utilization. International Conference on Information Systems, 10.'
bibtex: '@inproceedings{Leffrang_2023, title={AI Washing: The Framing Effect of
Labels on Algorithmic Advice Utilization}, number={10}, booktitle={International
Conference on Information Systems}, author={Leffrang, Dirk}, year={2023} }'
chicago: 'Leffrang, Dirk. “AI Washing: The Framing Effect of Labels on Algorithmic
Advice Utilization.” In International Conference on Information Systems,
2023.'
ieee: 'D. Leffrang, “AI Washing: The Framing Effect of Labels on Algorithmic Advice
Utilization,” in International Conference on Information Systems, Hyderabad,
India, 2023, no. 10.'
mla: 'Leffrang, Dirk. “AI Washing: The Framing Effect of Labels on Algorithmic Advice
Utilization.” International Conference on Information Systems, no. 10,
2023.'
short: 'D. Leffrang, in: International Conference on Information Systems, 2023.'
conference:
location: Hyderabad, India
name: International Conference on Information Systems (ICIS)
date_created: 2024-01-03T09:54:00Z
date_updated: 2024-01-10T09:53:41Z
department:
- _id: '196'
issue: '10'
keyword:
- Artificial Intelligence
- Algorithm Appreciation
- Framing
- Advice-taking
- Expertise
language:
- iso: eng
main_file_link:
- url: https://aisel.aisnet.org/icis2023/aiinbus/aiinbus/10
publication: International Conference on Information Systems
status: public
title: 'AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization'
type: conference
user_id: '51271'
year: '2023'
...
---
_id: '50118'
abstract:
- lang: eng
text: Despite the widespread use of machine learning algorithms, their effectiveness
is limited by a phenomenon known as algorithm aversion. Recent research concluded
that unobserved variables can cause algorithm aversion. However, the impact of
an unobserved variable on algorithm aversion remains unclear. Previous studies
focused on situations where humans had more variables available than algorithms.
We extend this research by conducting an online experiment with 94 participants,
systematically varying the number of observable variables to the advisor and the
advisor type. Surprisingly, our results did not confirm that an unobserved variable
had a negative effect on advice-taking. Instead, we found a positive impact in
an algorithm appreciation scenario. This study provides new insights into the
paradoxical behavior in which people weigh advice more despite having fewer variables,
as they correct for the advisor's errors. Practitioners should consider this behavior
when designing algorithms and account for user correction behavior.
author:
- first_name: Dirk
full_name: Leffrang, Dirk
id: '51271'
last_name: Leffrang
orcid: 0000-0001-9004-2391
citation:
ama: 'Leffrang D. The Broken Leg of Algorithm Appreciation: An Experimental Study
on the Effect of Unobserved Variables on Advice Utilization. In: Wirtschaftsinformatik
Conference. ; 2023.'
apa: 'Leffrang, D. (2023). The Broken Leg of Algorithm Appreciation: An Experimental
Study on the Effect of Unobserved Variables on Advice Utilization. Wirtschaftsinformatik
Conference, 19.'
bibtex: '@inproceedings{Leffrang_2023, title={The Broken Leg of Algorithm Appreciation:
An Experimental Study on the Effect of Unobserved Variables on Advice Utilization},
number={19}, booktitle={Wirtschaftsinformatik Conference}, author={Leffrang, Dirk},
year={2023} }'
chicago: 'Leffrang, Dirk. “The Broken Leg of Algorithm Appreciation: An Experimental
Study on the Effect of Unobserved Variables on Advice Utilization.” In Wirtschaftsinformatik
Conference, 2023.'
ieee: 'D. Leffrang, “The Broken Leg of Algorithm Appreciation: An Experimental Study
on the Effect of Unobserved Variables on Advice Utilization,” in Wirtschaftsinformatik
Conference, Paderborn, 2023, no. 19.'
mla: 'Leffrang, Dirk. “The Broken Leg of Algorithm Appreciation: An Experimental
Study on the Effect of Unobserved Variables on Advice Utilization.” Wirtschaftsinformatik
Conference, no. 19, 2023.'
short: 'D. Leffrang, in: Wirtschaftsinformatik Conference, 2023.'
conference:
location: Paderborn
name: Wirtschaftsinformatik
date_created: 2024-01-03T09:50:06Z
date_updated: 2024-01-10T09:53:24Z
department:
- _id: '196'
issue: '19'
keyword:
- Algorithm aversion
- Data
- Decision-making
- Advice-taking
- Human-Computer Interaction
language:
- iso: eng
main_file_link:
- url: 'https://aisel.aisnet.org/wi2023/19 '
publication: Wirtschaftsinformatik Conference
status: public
title: 'The Broken Leg of Algorithm Appreciation: An Experimental Study on the Effect
of Unobserved Variables on Advice Utilization'
type: conference
user_id: '51271'
year: '2023'
...
---
_id: '46310'
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) nearest neighbor relationships
of the input instance. To this end we theoretically derive minimum and maximum
values for properties of MSTs and k-nearest neighbor graphs (NNG) 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. 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
id: '105520'
last_name: Seiler
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
citation:
ama: Heins J, Bossek J, Pohl J, Seiler M, Trautmann H, Kerschke P. A study on the
effects of normalized TSP features for automated algorithm selection. Theoretical
Computer Science. 2023;940:123-145. doi:https://doi.org/10.1016/j.tcs.2022.10.019
apa: Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H., & Kerschke,
P. (2023). A study on the effects of normalized TSP features for automated algorithm
selection. Theoretical Computer Science, 940, 123–145. https://doi.org/10.1016/j.tcs.2022.10.019
bibtex: '@article{Heins_Bossek_Pohl_Seiler_Trautmann_Kerschke_2023, title={A study
on the effects of normalized TSP features for automated algorithm selection},
volume={940}, DOI={https://doi.org/10.1016/j.tcs.2022.10.019},
journal={Theoretical Computer Science}, author={Heins, Jonathan and Bossek, Jakob
and Pohl, Janina and Seiler, Moritz and Trautmann, Heike and Kerschke, Pascal},
year={2023}, pages={123–145} }'
chicago: 'Heins, Jonathan, Jakob Bossek, Janina Pohl, Moritz Seiler, Heike Trautmann,
and Pascal Kerschke. “A Study on the Effects of Normalized TSP Features for Automated
Algorithm Selection.” Theoretical Computer Science 940 (2023): 123–45.
https://doi.org/10.1016/j.tcs.2022.10.019.'
ieee: 'J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, and P. Kerschke, “A
study on the effects of normalized TSP features for automated algorithm selection,”
Theoretical Computer Science, vol. 940, pp. 123–145, 2023, doi: https://doi.org/10.1016/j.tcs.2022.10.019.'
mla: Heins, Jonathan, et al. “A Study on the Effects of Normalized TSP Features
for Automated Algorithm Selection.” Theoretical Computer Science, vol.
940, 2023, pp. 123–45, doi:https://doi.org/10.1016/j.tcs.2022.10.019.
short: J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical
Computer Science 940 (2023) 123–145.
date_created: 2023-08-04T07:18:38Z
date_updated: 2024-06-10T11:57:21Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.tcs.2022.10.019
intvolume: ' 940'
keyword:
- Feature normalization
- Algorithm selection
- Traveling salesperson problem
language:
- iso: eng
page: 123-145
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
status: public
title: A study on the effects of normalized TSP features for automated algorithm selection
type: journal_article
user_id: '15504'
volume: 940
year: '2023'
...
---
_id: '54428'
abstract:
- lang: eng
text: The article shows using the examples of the novels GRM. Brainfuck by Sibylle
Berg and Quality-Land by Marc-Uwe Kling how concepts of diversity can turn into
normative ideas about groups. Diversity as a positively valued descriptive category
of societies aims to influence ideas about the normality of language and the cultural
composition of societies. However, algorithmic systems based on artificial intelligence
in particular can contribute to the separation of constructed groups. Quite contrary
to the goals of an open and pluralistic society, ruptures in social groups can
be strengthened in this way.
author:
- first_name: Swen
full_name: Schulte Eickholt, Swen
id: '7117'
last_name: Schulte Eickholt
citation:
ama: 'Schulte Eickholt S. Normative Diversität? Nahe Zukunft bei Sibylle Berg und
Marc-Uwe Kling. In: Cosan L, Bazarkaya OK, Tekin H, eds. Germanistik im Wandel
1. Neue Einsichten und Perspektiven in der Literaturwissenschaft. Logos; 2023:65-75.'
apa: Schulte Eickholt, S. (2023). Normative Diversität? Nahe Zukunft bei Sibylle
Berg und Marc-Uwe Kling. In L. Cosan, O. K. Bazarkaya, & H. Tekin (Eds.),
Germanistik im Wandel 1. Neue Einsichten und Perspektiven in der Literaturwissenschaft
(pp. 65–75). Logos.
bibtex: '@inbook{Schulte Eickholt_2023, place={Berlin}, title={Normative Diversität?
Nahe Zukunft bei Sibylle Berg und Marc-Uwe Kling}, booktitle={Germanistik im Wandel
1. Neue Einsichten und Perspektiven in der Literaturwissenschaft}, publisher={Logos},
author={Schulte Eickholt, Swen}, editor={Cosan, Leyla and Bazarkaya, Onur Kemal
and Tekin, Habib}, year={2023}, pages={65–75} }'
chicago: 'Schulte Eickholt, Swen. “Normative Diversität? Nahe Zukunft bei Sibylle
Berg und Marc-Uwe Kling.” In Germanistik im Wandel 1. Neue Einsichten und Perspektiven
in der Literaturwissenschaft, edited by Leyla Cosan, Onur Kemal Bazarkaya,
and Habib Tekin, 65–75. Berlin: Logos, 2023.'
ieee: 'S. Schulte Eickholt, “Normative Diversität? Nahe Zukunft bei Sibylle Berg
und Marc-Uwe Kling,” in Germanistik im Wandel 1. Neue Einsichten und Perspektiven
in der Literaturwissenschaft, L. Cosan, O. K. Bazarkaya, and H. Tekin, Eds.
Berlin: Logos, 2023, pp. 65–75.'
mla: Schulte Eickholt, Swen. “Normative Diversität? Nahe Zukunft bei Sibylle Berg
und Marc-Uwe Kling.” Germanistik im Wandel 1. Neue Einsichten und Perspektiven
in der Literaturwissenschaft, edited by Leyla Cosan et al., Logos, 2023, pp.
65–75.
short: 'S. Schulte Eickholt, in: L. Cosan, O.K. Bazarkaya, H. Tekin (Eds.), Germanistik
im Wandel 1. Neue Einsichten und Perspektiven in der Literaturwissenschaft, Logos,
Berlin, 2023, pp. 65–75.'
date_created: 2024-05-23T09:25:19Z
date_updated: 2024-07-31T07:51:08Z
department:
- _id: '465'
editor:
- first_name: Leyla
full_name: Cosan, Leyla
last_name: Cosan
- first_name: Onur Kemal
full_name: Bazarkaya, Onur Kemal
last_name: Bazarkaya
- first_name: Habib
full_name: Tekin, Habib
last_name: Tekin
keyword:
- diversity
- normality
- contemporary literature
- algorithm
- distopia
- Diversität
- Normalität
- Gegenwartsliteratur
- Algorithmus
- Dystopie
language:
- iso: ger
page: 65-75
place: Berlin
publication: Germanistik im Wandel 1. Neue Einsichten und Perspektiven in der Literaturwissenschaft
publication_status: published
publisher: Logos
quality_controlled: '1'
status: public
title: Normative Diversität? Nahe Zukunft bei Sibylle Berg und Marc-Uwe Kling
type: book_chapter
user_id: '7117'
year: '2023'
...
---
_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: '48897'
abstract:
- lang: eng
text: 'In this work we focus on the well-known Euclidean Traveling Salesperson Problem
(TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in
the context of per-instance algorithm selection (AS). We evolve instances with
nodes where the solvers show strongly different performance profiles. These instances
serve as a basis for an exploratory study on the identification of well-discriminating
problem characteristics (features). Our results in a nutshell: we show that even
though (1) promising features exist, (2) these are in line with previous results
from the literature, and (3) models trained with these features are more accurate
than models adopting sophisticated feature selection methods, the advantage is
not close to the virtual best solver in terms of penalized average runtime and
so is the performance gain over the single best solver. However, we show that
a feature-free deep neural network based approach solely based on visual representation
of the instances already matches classical AS model results and thus shows huge
potential for future studies.'
author:
- first_name: Moritz
full_name: Seiler, Moritz
last_name: Seiler
- first_name: Janina
full_name: Pohl, Janina
last_name: Pohl
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Seiler M, Pohl J, Bossek J, Kerschke P, Trautmann H. Deep Learning as a Competitive
Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson
Problem. In: Parallel Problem Solving from {Nature} (PPSN XVI). Springer-Verlag;
2020:48–64. doi:10.1007/978-3-030-58112-1_4'
apa: Seiler, M., Pohl, J., Bossek, J., Kerschke, P., & Trautmann, H. (2020).
Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection
on the Traveling Salesperson Problem. Parallel Problem Solving from {Nature}
(PPSN XVI), 48–64. https://doi.org/10.1007/978-3-030-58112-1_4
bibtex: '@inproceedings{Seiler_Pohl_Bossek_Kerschke_Trautmann_2020, place={Berlin,
Heidelberg}, title={Deep Learning as a Competitive Feature-Free Approach for Automated
Algorithm Selection on the Traveling Salesperson Problem}, DOI={10.1007/978-3-030-58112-1_4},
booktitle={Parallel Problem Solving from {Nature} (PPSN XVI)}, publisher={Springer-Verlag},
author={Seiler, Moritz and Pohl, Janina and Bossek, Jakob and Kerschke, Pascal
and Trautmann, Heike}, year={2020}, pages={48–64} }'
chicago: 'Seiler, Moritz, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike
Trautmann. “Deep Learning as a Competitive Feature-Free Approach for Automated
Algorithm Selection on the Traveling Salesperson Problem.” In Parallel Problem
Solving from {Nature} (PPSN XVI), 48–64. Berlin, Heidelberg: Springer-Verlag,
2020. https://doi.org/10.1007/978-3-030-58112-1_4.'
ieee: 'M. Seiler, J. Pohl, J. Bossek, P. Kerschke, and H. Trautmann, “Deep Learning
as a Competitive Feature-Free Approach for Automated Algorithm Selection on the
Traveling Salesperson Problem,” in Parallel Problem Solving from {Nature} (PPSN
XVI), 2020, pp. 48–64, doi: 10.1007/978-3-030-58112-1_4.'
mla: Seiler, Moritz, et al. “Deep Learning as a Competitive Feature-Free Approach
for Automated Algorithm Selection on the Traveling Salesperson Problem.” Parallel
Problem Solving from {Nature} (PPSN XVI), Springer-Verlag, 2020, pp. 48–64,
doi:10.1007/978-3-030-58112-1_4.
short: 'M. Seiler, J. Pohl, J. Bossek, P. Kerschke, H. Trautmann, in: Parallel Problem
Solving from {Nature} (PPSN XVI), Springer-Verlag, Berlin, Heidelberg, 2020, pp.
48–64.'
date_created: 2023-11-14T15:59:00Z
date_updated: 2023-12-13T10:49:45Z
department:
- _id: '819'
doi: 10.1007/978-3-030-58112-1_4
extern: '1'
keyword:
- Automated algorithm selection
- Deep learning
- Feature-based approaches
- Traveling Salesperson Problem
language:
- iso: eng
page: 48–64
place: Berlin, Heidelberg
publication: Parallel Problem Solving from {Nature} (PPSN XVI)
publication_identifier:
isbn:
- 978-3-030-58111-4
publisher: Springer-Verlag
status: public
title: Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm
Selection on the Traveling Salesperson Problem
type: conference
user_id: '102979'
year: '2020'
...
---
_id: '48848'
abstract:
- lang: eng
text: We build upon a recently proposed multi-objective view onto performance measurement
of single-objective stochastic solvers. The trade-off between the fraction of
failed runs and the mean runtime of successful runs \textendash both to be minimized
\textendash is directly analyzed based on a study on algorithm selection of inexact
state-of-the-art solvers for the famous Traveling Salesperson Problem (TSP). Moreover,
we adopt the hypervolume indicator (HV) commonly used in multi-objective optimization
for simultaneously assessing both conflicting objectives and investigate relations
to commonly used performance indicators, both theoretically and empirically. Next
to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV
measure is used as a core concept within the construction of per-instance algorithm
selection models offering interesting insights into complementary behavior of
inexact TSP solvers. \textbullet The multi-objective perspective is naturally
generalizable to multiple objectives. \textbullet Proof of relationship between
HV and the PAR in the considered bi-objective space. \textbullet New insights
into complementary behavior of stochastic optimization algorithms.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: Bossek J, Kerschke P, Trautmann H. A Multi-Objective Perspective on Performance
Assessment and Automated Selection of Single-Objective Optimization Algorithms.
Applied Soft Computing. 2020;88(C). doi:10.1016/j.asoc.2019.105901
apa: Bossek, J., Kerschke, P., & Trautmann, H. (2020). A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms. Applied Soft Computing, 88(C). https://doi.org/10.1016/j.asoc.2019.105901
bibtex: '@article{Bossek_Kerschke_Trautmann_2020, title={A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms}, volume={88}, DOI={10.1016/j.asoc.2019.105901},
number={C}, journal={Applied Soft Computing}, author={Bossek, Jakob and Kerschke,
Pascal and Trautmann, Heike}, year={2020} }'
chicago: Bossek, Jakob, Pascal Kerschke, and Heike Trautmann. “A Multi-Objective
Perspective on Performance Assessment and Automated Selection of Single-Objective
Optimization Algorithms.” Applied Soft Computing 88, no. C (2020). https://doi.org/10.1016/j.asoc.2019.105901.
ieee: 'J. Bossek, P. Kerschke, and H. Trautmann, “A Multi-Objective Perspective
on Performance Assessment and Automated Selection of Single-Objective Optimization
Algorithms,” Applied Soft Computing, vol. 88, no. C, 2020, doi: 10.1016/j.asoc.2019.105901.'
mla: Bossek, Jakob, et al. “A Multi-Objective Perspective on Performance Assessment
and Automated Selection of Single-Objective Optimization Algorithms.” Applied
Soft Computing, vol. 88, no. C, 2020, doi:10.1016/j.asoc.2019.105901.
short: J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020).
date_created: 2023-11-14T15:58:53Z
date_updated: 2023-12-13T10:52:17Z
department:
- _id: '819'
doi: 10.1016/j.asoc.2019.105901
intvolume: ' 88'
issue: C
keyword:
- Algorithm selection
- Combinatorial optimization
- Multi-objective optimization
- Performance measurement
- Traveling Salesperson Problem
language:
- iso: eng
publication: Applied Soft Computing
publication_identifier:
issn:
- 1568-4946
status: public
title: A Multi-Objective Perspective on Performance Assessment and Automated Selection
of Single-Objective Optimization Algorithms
type: journal_article
user_id: '102979'
volume: 88
year: '2020'
...
---
_id: '46334'
abstract:
- lang: eng
text: We build upon a recently proposed multi-objective view onto performance measurement
of single-objective stochastic solvers. The trade-off between the fraction of
failed runs and the mean runtime of successful runs – both to be minimized – is
directly analyzed based on a study on algorithm selection of inexact state-of-the-art
solvers for the famous Traveling Salesperson Problem (TSP). Moreover, we adopt
the hypervolume indicator (HV) commonly used in multi-objective optimization for
simultaneously assessing both conflicting objectives and investigate relations
to commonly used performance indicators, both theoretically and empirically. Next
to Penalized Average Runtime (PAR) and Penalized Quantile Runtime (PQR), the HV
measure is used as a core concept within the construction of per-instance algorithm
selection models offering interesting insights into complementary behavior of
inexact TSP solvers.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Heike
full_name: Trautmann, Heike
id: '100740'
last_name: Trautmann
orcid: 0000-0002-9788-8282
citation:
ama: Bossek J, Kerschke P, Trautmann H. A multi-objective perspective on performance
assessment and automated selection of single-objective optimization algorithms.
Applied Soft Computing. 2020;88:105901. doi:https://doi.org/10.1016/j.asoc.2019.105901
apa: Bossek, J., Kerschke, P., & Trautmann, H. (2020). A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms. Applied Soft Computing, 88, 105901. https://doi.org/10.1016/j.asoc.2019.105901
bibtex: '@article{Bossek_Kerschke_Trautmann_2020, title={A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms}, volume={88}, DOI={https://doi.org/10.1016/j.asoc.2019.105901},
journal={Applied Soft Computing}, author={Bossek, Jakob and Kerschke, Pascal and
Trautmann, Heike}, year={2020}, pages={105901} }'
chicago: 'Bossek, Jakob, Pascal Kerschke, and Heike Trautmann. “A Multi-Objective
Perspective on Performance Assessment and Automated Selection of Single-Objective
Optimization Algorithms.” Applied Soft Computing 88 (2020): 105901. https://doi.org/10.1016/j.asoc.2019.105901.'
ieee: 'J. Bossek, P. Kerschke, and H. Trautmann, “A multi-objective perspective
on performance assessment and automated selection of single-objective optimization
algorithms,” Applied Soft Computing, vol. 88, p. 105901, 2020, doi: https://doi.org/10.1016/j.asoc.2019.105901.'
mla: Bossek, Jakob, et al. “A Multi-Objective Perspective on Performance Assessment
and Automated Selection of Single-Objective Optimization Algorithms.” Applied
Soft Computing, vol. 88, 2020, p. 105901, doi:https://doi.org/10.1016/j.asoc.2019.105901.
short: J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020) 105901.
date_created: 2023-08-04T07:42:26Z
date_updated: 2024-06-10T12:00:46Z
department:
- _id: '34'
- _id: '819'
doi: https://doi.org/10.1016/j.asoc.2019.105901
intvolume: ' 88'
keyword:
- Algorithm selection
- Multi-objective optimization
- Performance measurement
- Combinatorial optimization
- Traveling Salesperson Problem
language:
- iso: eng
page: '105901'
publication: Applied Soft Computing
publication_identifier:
issn:
- 1568-4946
status: public
title: A multi-objective perspective on performance assessment and automated selection
of single-objective optimization algorithms
type: journal_article
user_id: '15504'
volume: 88
year: '2020'
...
---
_id: '6512'
abstract:
- lang: eng
text: Scheduling problems are essential for decision making in many academic disciplines,
including operations management, computer science, and information systems. Since
many scheduling problems are NP-hard in the strong sense, there is only limited
research on exact algorithms and how their efficiency scales when implemented
on parallel computing architectures. We address this gap by (1) adapting an exact
branch-and-price algorithm to a parallel machine scheduling problem on unrelated
machines with sequence- and machine-dependent setup times, (2) parallelizing the
adapted algorithm by implementing a distributed-memory parallelization with a
master/worker approach, and (3) conducting extensive computational experiments
using up to 960 MPI processes on a modern high performance computing cluster.
With our experiments, we show that the efficiency of our parallelization approach
can lead to superlinear speedup but can vary substantially between instances.
We further show that the wall time of serial execution can be substantially reduced
through our parallelization, in some cases from 94 hours to less than six minutes
when our algorithm is executed on 960 processes.
author:
- first_name: Gerhard
full_name: Rauchecker, Gerhard
last_name: Rauchecker
- first_name: Guido
full_name: Schryen, Guido
id: '72850'
last_name: Schryen
citation:
ama: 'Rauchecker G, Schryen G. Using High Performance Computing for Unrelated Parallel
Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational
Evaluation of a Parallel Branch-and-Price Algorithm. Computers & Operations
Research. 2019;(104):338-357.'
apa: 'Rauchecker, G., & Schryen, G. (2019). Using High Performance Computing
for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times:
Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm.
Computers & Operations Research, (104), 338–357.'
bibtex: '@article{Rauchecker_Schryen_2019, title={Using High Performance Computing
for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times:
Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm},
number={104}, journal={Computers & Operations Research}, publisher={Elsevier},
author={Rauchecker, Gerhard and Schryen, Guido}, year={2019}, pages={338–357}
}'
chicago: 'Rauchecker, Gerhard, and Guido Schryen. “Using High Performance Computing
for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times:
Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm.”
Computers & Operations Research, no. 104 (2019): 338–57.'
ieee: 'G. Rauchecker and G. Schryen, “Using High Performance Computing for Unrelated
Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and
Computational Evaluation of a Parallel Branch-and-Price Algorithm,” Computers
& Operations Research, no. 104, pp. 338–357, 2019.'
mla: 'Rauchecker, Gerhard, and Guido Schryen. “Using High Performance Computing
for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times:
Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm.”
Computers & Operations Research, no. 104, Elsevier, 2019, pp. 338–57.'
short: G. Rauchecker, G. Schryen, Computers & Operations Research (2019) 338–357.
date_created: 2019-01-08T13:50:44Z
date_updated: 2022-01-06T07:03:08Z
ddc:
- '000'
department:
- _id: '277'
file:
- access_level: open_access
content_type: application/pdf
creator: hsiemes
date_created: 2019-01-08T14:03:53Z
date_updated: 2019-01-08T14:03:53Z
file_id: '6513'
file_name: cor-parallel-bp-for-upmsp.pdf
file_size: 4153528
relation: main_file
file_date_updated: 2019-01-08T14:03:53Z
has_accepted_license: '1'
issue: '104'
keyword:
- parallel machine scheduling with setup times
- parallel branch-and-price algorithm
- high performance computing
- master/worker parallelization
language:
- iso: eng
oa: '1'
page: 338-357
publication: Computers & Operations Research
publisher: Elsevier
status: public
title: 'Using High Performance Computing for Unrelated Parallel Machine Scheduling
with Sequence-Dependent Setup Times: Development and Computational Evaluation of
a Parallel Branch-and-Price Algorithm'
type: journal_article
user_id: '61579'
year: '2019'
...
---
_id: '48875'
abstract:
- lang: eng
text: A multiobjective perspective onto common performance measures such as the
PAR10 score or the expected runtime of single-objective stochastic solvers is
presented by directly investigating the tradeoff between the fraction of failed
runs and the average runtime. Multi-objective indicators operating in the bi-objective
space allow for an overall performance comparison on a set of instances paving
the way for instance-based automated algorithm selection techniques.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Trautmann H. Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time. In: Battiti R, Brunato M, Kotsireas I, Pardalos
PM, eds. Learning and Intelligent Optimization. Lecture Notes in Computer
Science. Springer International Publishing; 2019:215–219. doi:10.1007/978-3-030-05348-2_19'
apa: 'Bossek, J., & Trautmann, H. (2019). Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time. In R. Battiti, M. Brunato, I.
Kotsireas, & P. M. Pardalos (Eds.), Learning and Intelligent Optimization
(pp. 215–219). Springer International Publishing. https://doi.org/10.1007/978-3-030-05348-2_19'
bibtex: '@inproceedings{Bossek_Trautmann_2019, place={Cham}, series={Lecture Notes
in Computer Science}, title={Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time}, DOI={10.1007/978-3-030-05348-2_19},
booktitle={Learning and Intelligent Optimization}, publisher={Springer International
Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Battiti, Roberto
and Brunato, Mauro and Kotsireas, Ilias and Pardalos, Panos M.}, year={2019},
pages={215–219}, collection={Lecture Notes in Computer Science} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time.” In Learning and Intelligent
Optimization, edited by Roberto Battiti, Mauro Brunato, Ilias Kotsireas, and
Panos M. Pardalos, 215–219. Lecture Notes in Computer Science. Cham: Springer
International Publishing, 2019. https://doi.org/10.1007/978-3-030-05348-2_19.'
ieee: 'J. Bossek and H. Trautmann, “Multi-Objective Performance Measurement: Alternatives
to PAR10 and Expected Running Time,” in Learning and Intelligent Optimization,
2019, pp. 215–219, doi: 10.1007/978-3-030-05348-2_19.'
mla: 'Bossek, Jakob, and Heike Trautmann. “Multi-Objective Performance Measurement:
Alternatives to PAR10 and Expected Running Time.” Learning and Intelligent
Optimization, edited by Roberto Battiti et al., Springer International Publishing,
2019, pp. 215–219, doi:10.1007/978-3-030-05348-2_19.'
short: 'J. Bossek, H. Trautmann, in: R. Battiti, M. Brunato, I. Kotsireas, P.M.
Pardalos (Eds.), Learning and Intelligent Optimization, Springer International
Publishing, Cham, 2019, pp. 215–219.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:32Z
department:
- _id: '819'
doi: 10.1007/978-3-030-05348-2_19
editor:
- first_name: Roberto
full_name: Battiti, Roberto
last_name: Battiti
- first_name: Mauro
full_name: Brunato, Mauro
last_name: Brunato
- first_name: Ilias
full_name: Kotsireas, Ilias
last_name: Kotsireas
- first_name: Panos M.
full_name: Pardalos, Panos M.
last_name: Pardalos
extern: '1'
keyword:
- Algorithm selection
- Performance measurement
language:
- iso: eng
page: 215–219
place: Cham
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-030-05348-2
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: 'Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected
Running Time'
type: conference
user_id: '102979'
year: '2019'
...
---
_id: '3422'
abstract:
- lang: eng
text: "We study the consensus problem in a synchronous distributed system of n nodes
under an adaptive adversary that has a slightly outdated view of the system and
can block all incoming and outgoing communication of a constant fraction of the
nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing
that any consensus algorithm that is resilient against a linear number of crash
faults requires $\\tilde \\Omega(\\sqrt n)$ rounds in an n-node network against
an adaptive adversary, we consider a late adaptive adversary, who has full knowledge
of the network state at the beginning of the previous round and unlimited computational
power, but is oblivious to the current state of the nodes. \r\n\r\nOur main contributions
are randomized distributed algorithms that achieve consensus with high probability
among all except a small constant fraction of the nodes (i.e., \"almost-everywhere'')
against a late adaptive adversary who can block up to ε n$ nodes in each round,
for a small constant ε >0$. Our first protocol achieves binary almost-everywhere
consensus and also guarantees a decision on the majority input value, thus ensuring
plurality consensus. We also present an algorithm that achieves the same time
complexity for multi-value consensus. Both of our algorithms succeed in $O(log
n)$ rounds with high probability, thus showing an exponential gap to the $\\tilde\\Omega(\\sqrt
n)$ lower bound of Ben-Or and Bar-Joseph for strongly adaptive crash-failure adversaries,
which can be strengthened to $\\Omega(n)$ when allowing the adversary to block
nodes instead of permanently crashing them. Our algorithms are scalable to large
systems as each node contacts only an (amortized) constant number of peers in
each communication round. We show that our algorithms are optimal up to constant
(resp.\\ sub-logarithmic) factors by proving that every almost-everywhere consensus
protocol takes $\\Omega(log_d n)$ rounds in the worst case, where d is an upper
bound on the number of communication requests initiated per node in each round.
We complement our theoretical results with an experimental evaluation of the binary
almost-everywhere consensus protocol revealing a short convergence time even against
an adversary blocking a large fraction of nodes."
author:
- first_name: Peter
full_name: Robinson, Peter
last_name: Robinson
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
citation:
ama: 'Robinson P, Scheideler C, Setzer A. Breaking the $\tilde\Omega(\sqrt{n})$
Barrier: Fast Consensus under a Late Adversary. In: Proceedings of the 30th
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). doi:10.1145/3210377.3210399'
apa: 'Robinson, P., Scheideler, C., & Setzer, A. (n.d.). Breaking the $\tilde\Omega(\sqrt{n})$
Barrier: Fast Consensus under a Late Adversary. In Proceedings of the 30th
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). Wien.
https://doi.org/10.1145/3210377.3210399'
bibtex: '@inproceedings{Robinson_Scheideler_Setzer, title={Breaking the $\tilde\Omega(\sqrt{n})$
Barrier: Fast Consensus under a Late Adversary}, DOI={10.1145/3210377.3210399},
booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Robinson, Peter and Scheideler, Christian and
Setzer, Alexander} }'
chicago: 'Robinson, Peter, Christian Scheideler, and Alexander Setzer. “Breaking
the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.”
In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), n.d. https://doi.org/10.1145/3210377.3210399.'
ieee: 'P. Robinson, C. Scheideler, and A. Setzer, “Breaking the $\tilde\Omega(\sqrt{n})$
Barrier: Fast Consensus under a Late Adversary,” in Proceedings of the 30th
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Wien.'
mla: 'Robinson, Peter, et al. “Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast
Consensus under a Late Adversary.” Proceedings of the 30th ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA), doi:10.1145/3210377.3210399.'
short: 'P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), n.d.'
conference:
end_date: 2018-07-18
location: Wien
name: 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
start_date: 2018-07-16
date_created: 2018-07-04T08:55:45Z
date_updated: 2022-01-06T06:59:16Z
ddc:
- '040'
department:
- _id: '79'
- _id: '34'
- _id: '7'
doi: 10.1145/3210377.3210399
file:
- access_level: closed
content_type: application/pdf
creator: asetzer
date_created: 2018-10-31T13:30:40Z
date_updated: 2018-10-31T13:30:40Z
file_id: '5215'
file_name: p173-robinson.pdf
file_size: 1675407
relation: main_file
success: 1
file_date_updated: 2018-10-31T13:30:40Z
has_accepted_license: '1'
keyword:
- distributed consensus
- randomized algorithm
- adaptive adversary
- complexity lower bound
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '4'
name: SFB 901 - Project Area C
- _id: '13'
name: SFB 901 - Subproject C1
publication: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
publication_identifier:
isbn:
- 978-1-4503-5799-9/18/07
publication_status: accepted
status: public
title: 'Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late
Adversary'
type: conference
user_id: '11108'
year: '2018'
...
---
_id: '48885'
abstract:
- lang: eng
text: Performance comparisons of optimization algorithms are heavily influenced
by the underlying indicator(s). In this paper we investigate commonly used performance
indicators for single-objective stochastic solvers, such as the Penalized Average
Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark
performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a
methodology for analyzing the effects of (usually heuristically set) indicator
parametrizations - such as the penalty factor and the method used for aggregating
across multiple runs - w.r.t. the robustness of the considered optimization algorithms.
author:
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Kerschke P, Bossek J, Trautmann H. Parameterization of State-of-the-Art Performance
Indicators: A Robustness Study Based on Inexact TSP Solvers. In: Proceedings
of the Genetic and Evolutionary Computation Conference Companion. GECCO’18.
Association for Computing Machinery; 2018:1737–1744. doi:10.1145/3205651.3208233'
apa: 'Kerschke, P., Bossek, J., & Trautmann, H. (2018). Parameterization of
State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP
Solvers. Proceedings of the Genetic and Evolutionary Computation Conference
Companion, 1737–1744. https://doi.org/10.1145/3205651.3208233'
bibtex: '@inproceedings{Kerschke_Bossek_Trautmann_2018, place={New York, NY, USA},
series={GECCO’18}, title={Parameterization of State-of-the-Art Performance Indicators:
A Robustness Study Based on Inexact TSP Solvers}, DOI={10.1145/3205651.3208233},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference
Companion}, publisher={Association for Computing Machinery}, author={Kerschke,
Pascal and Bossek, Jakob and Trautmann, Heike}, year={2018}, pages={1737–1744},
collection={GECCO’18} }'
chicago: 'Kerschke, Pascal, Jakob Bossek, and Heike Trautmann. “Parameterization
of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact
TSP Solvers.” In Proceedings of the Genetic and Evolutionary Computation Conference
Companion, 1737–1744. GECCO’18. New York, NY, USA: Association for Computing
Machinery, 2018. https://doi.org/10.1145/3205651.3208233.'
ieee: 'P. Kerschke, J. Bossek, and H. Trautmann, “Parameterization of State-of-the-Art
Performance Indicators: A Robustness Study Based on Inexact TSP Solvers,” in Proceedings
of the Genetic and Evolutionary Computation Conference Companion, 2018, pp.
1737–1744, doi: 10.1145/3205651.3208233.'
mla: 'Kerschke, Pascal, et al. “Parameterization of State-of-the-Art Performance
Indicators: A Robustness Study Based on Inexact TSP Solvers.” Proceedings of
the Genetic and Evolutionary Computation Conference Companion, Association
for Computing Machinery, 2018, pp. 1737–1744, doi:10.1145/3205651.3208233.'
short: 'P. Kerschke, J. Bossek, H. Trautmann, in: Proceedings of the Genetic and
Evolutionary Computation Conference Companion, Association for Computing Machinery,
New York, NY, USA, 2018, pp. 1737–1744.'
date_created: 2023-11-14T15:58:59Z
date_updated: 2023-12-13T10:48:38Z
department:
- _id: '819'
doi: 10.1145/3205651.3208233
extern: '1'
keyword:
- algorithm selection
- optimization
- performance measures
- transportation
- travelling salesperson problem
language:
- iso: eng
page: 1737–1744
place: New York, NY, USA
publication: Proceedings of the Genetic and Evolutionary Computation Conference Companion
publication_identifier:
isbn:
- 978-1-4503-5764-7
publisher: Association for Computing Machinery
series_title: GECCO’18
status: public
title: 'Parameterization of State-of-the-Art Performance Indicators: A Robustness
Study Based on Inexact TSP Solvers'
type: conference
user_id: '102979'
year: '2018'
...
---
_id: '48884'
abstract:
- lang: eng
text: The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard
problems. Over the years, many different solution approaches and solvers have
been developed. For the first time, we directly compare five state-of-the-art
inexact solvers\textemdash namely, LKH, EAX, restart variants of those, and MAOS\textemdash
on a large set of well-known benchmark instances and demonstrate complementary
performance, in that different instances may be solved most effectively by different
algorithms. We leverage this complementarity to build an algorithm selector, which
selects the best TSP solver on a per-instance basis and thus achieves significantly
improved performance compared to the single best solver, representing an advance
in the state of the art in solving the Euclidean TSP. Our in-depth analysis of
the selectors provides insight into what drives this performance improvement.
author:
- first_name: Pascal
full_name: Kerschke, Pascal
last_name: Kerschke
- first_name: Lars
full_name: Kotthoff, Lars
last_name: Kotthoff
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Holger H.
full_name: Hoos, Holger H.
last_name: Hoos
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: Kerschke P, Kotthoff L, Bossek J, Hoos HH, Trautmann H. Leveraging TSP Solver
Complementarity through Machine Learning. Evolutionary Computation. 2018;26(4):597–620.
doi:10.1162/evco_a_00215
apa: Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., & Trautmann, H. (2018).
Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary
Computation, 26(4), 597–620. https://doi.org/10.1162/evco_a_00215
bibtex: '@article{Kerschke_Kotthoff_Bossek_Hoos_Trautmann_2018, title={Leveraging
TSP Solver Complementarity through Machine Learning}, volume={26}, DOI={10.1162/evco_a_00215},
number={4}, journal={Evolutionary Computation}, author={Kerschke, Pascal and Kotthoff,
Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}, year={2018},
pages={597–620} }'
chicago: 'Kerschke, Pascal, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike
Trautmann. “Leveraging TSP Solver Complementarity through Machine Learning.” Evolutionary
Computation 26, no. 4 (2018): 597–620. https://doi.org/10.1162/evco_a_00215.'
ieee: 'P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging
TSP Solver Complementarity through Machine Learning,” Evolutionary Computation,
vol. 26, no. 4, pp. 597–620, 2018, doi: 10.1162/evco_a_00215.'
mla: Kerschke, Pascal, et al. “Leveraging TSP Solver Complementarity through Machine
Learning.” Evolutionary Computation, vol. 26, no. 4, 2018, pp. 597–620,
doi:10.1162/evco_a_00215.
short: P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary
Computation 26 (2018) 597–620.
date_created: 2023-11-14T15:58:58Z
date_updated: 2023-12-13T10:51:26Z
department:
- _id: '819'
doi: 10.1162/evco_a_00215
intvolume: ' 26'
issue: '4'
keyword:
- automated algorithm selection
- machine learning.
- performance modeling
- Travelling Salesperson Problem
language:
- iso: eng
page: 597–620
publication: Evolutionary Computation
publication_identifier:
issn:
- 1063-6560
status: public
title: Leveraging TSP Solver Complementarity through Machine Learning
type: journal_article
user_id: '102979'
volume: 26
year: '2018'
...
---
_id: '1590'
abstract:
- lang: eng
text: "We present the submatrix method, a highly parallelizable method for the approximate
calculation of inverse p-th roots of large sparse symmetric matrices which are
required in different scientific applications. Following the idea of Approximate
Computing, we allow imprecision in the final result in order to utilize the sparsity
of the input matrix and to allow massively parallel execution. For an n x n matrix,
the proposed algorithm allows to distribute the calculations over n nodes with
only little communication overhead. The result matrix exhibits the same sparsity
pattern as the input matrix, allowing for efficient reuse of allocated data structures.\r\n\r\nWe
evaluate the algorithm with respect to the error that it introduces into calculated
results, as well as its performance and scalability. We demonstrate that the error
is relatively limited for well-conditioned matrices and that results are still
valuable for error-resilient applications like preconditioning even for ill-conditioned
matrices. We discuss the execution time and scaling of the algorithm on a theoretical
level and present a distributed implementation of the algorithm using MPI and
OpenMP. We demonstrate the scalability of this implementation by running it on
a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup
of 665x compared to single-threaded execution."
author:
- first_name: Michael
full_name: Lass, Michael
id: '24135'
last_name: Lass
orcid: 0000-0002-5708-7632
- first_name: Stephan
full_name: Mohr, Stephan
last_name: Mohr
- first_name: Hendrik
full_name: Wiebeler, Hendrik
last_name: Wiebeler
- first_name: Thomas
full_name: Kühne, Thomas
id: '49079'
last_name: Kühne
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
citation:
ama: 'Lass M, Mohr S, Wiebeler H, Kühne T, Plessl C. A Massively Parallel Algorithm
for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices.
In: Proc. Platform for Advanced Scientific Computing (PASC) Conference.
ACM; 2018. doi:10.1145/3218176.3218231'
apa: Lass, M., Mohr, S., Wiebeler, H., Kühne, T., & Plessl, C. (2018). A Massively
Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large
Sparse Matrices. Proc. Platform for Advanced Scientific Computing (PASC) Conference.
Platform for Advanced Scientific Computing Conference (PASC), Basel, Switzerland.
https://doi.org/10.1145/3218176.3218231
bibtex: '@inproceedings{Lass_Mohr_Wiebeler_Kühne_Plessl_2018, place={New York, NY,
USA}, title={A Massively Parallel Algorithm for the Approximate Calculation of
Inverse p-th Roots of Large Sparse Matrices}, DOI={10.1145/3218176.3218231},
booktitle={Proc. Platform for Advanced Scientific Computing (PASC) Conference},
publisher={ACM}, author={Lass, Michael and Mohr, Stephan and Wiebeler, Hendrik
and Kühne, Thomas and Plessl, Christian}, year={2018} }'
chicago: 'Lass, Michael, Stephan Mohr, Hendrik Wiebeler, Thomas Kühne, and Christian
Plessl. “A Massively Parallel Algorithm for the Approximate Calculation of Inverse
P-Th Roots of Large Sparse Matrices.” In Proc. Platform for Advanced Scientific
Computing (PASC) Conference. New York, NY, USA: ACM, 2018. https://doi.org/10.1145/3218176.3218231.'
ieee: 'M. Lass, S. Mohr, H. Wiebeler, T. Kühne, and C. Plessl, “A Massively Parallel
Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse
Matrices,” presented at the Platform for Advanced Scientific Computing Conference
(PASC), Basel, Switzerland, 2018, doi: 10.1145/3218176.3218231.'
mla: Lass, Michael, et al. “A Massively Parallel Algorithm for the Approximate Calculation
of Inverse P-Th Roots of Large Sparse Matrices.” Proc. Platform for Advanced
Scientific Computing (PASC) Conference, ACM, 2018, doi:10.1145/3218176.3218231.
short: 'M. Lass, S. Mohr, H. Wiebeler, T. Kühne, C. Plessl, in: Proc. Platform for
Advanced Scientific Computing (PASC) Conference, ACM, New York, NY, USA, 2018.'
conference:
end_date: 2018-07-04
location: Basel, Switzerland
name: Platform for Advanced Scientific Computing Conference (PASC)
start_date: 2018-07-02
date_created: 2018-03-22T10:53:01Z
date_updated: 2023-09-26T11:48:12Z
department:
- _id: '27'
- _id: '518'
- _id: '304'
doi: 10.1145/3218176.3218231
external_id:
arxiv:
- '1710.10899'
keyword:
- approximate computing
- linear algebra
- matrix inversion
- matrix p-th roots
- numeric algorithm
- parallel computing
language:
- iso: eng
place: New York, NY, USA
project:
- _id: '32'
grant_number: PL 595/2-1 / 320898746
name: Performance and Efficiency in HPC with Custom Computing
- _id: '52'
name: Computing Resources Provided by the Paderborn Center for Parallel Computing
publication: Proc. Platform for Advanced Scientific Computing (PASC) Conference
publication_identifier:
isbn:
- 978-1-4503-5891-0/18/07
publisher: ACM
quality_controlled: '1'
status: public
title: A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th
Roots of Large Sparse Matrices
type: conference
user_id: '15278'
year: '2018'
...
---
_id: '17652'
author:
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Stojan
full_name: Trajanovski, Stojan
last_name: Trajanovski
- first_name: Paola
full_name: Grosso, Paola
last_name: Grosso
- first_name: Cees
full_name: de Laat, Cees
last_name: de Laat
citation:
ama: 'Polevoy G, Trajanovski S, Grosso P, de Laat C. Filtering Undesirable Flows
in Networks. In: Combinatorial Optimization and Applications: 11th International
Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part
I. Lecture Notes in Computer Science. Cham: Springer International Publishing;
2017:3-17. doi:10.1007/978-3-319-71150-8_1'
apa: 'Polevoy, G., Trajanovski, S., Grosso, P., & de Laat, C. (2017). Filtering
Undesirable Flows in Networks. In Combinatorial Optimization and Applications:
11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017,
Proceedings, Part I (pp. 3–17). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-71150-8_1'
bibtex: '@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2017, place={Cham}, series={Lecture
Notes in Computer Science}, title={Filtering Undesirable Flows in Networks}, DOI={10.1007/978-3-319-71150-8_1},
booktitle={Combinatorial Optimization and Applications: 11th International Conference,
COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}, publisher={Springer
International Publishing}, author={Polevoy, Gleb and Trajanovski, Stojan and Grosso,
Paola and de Laat, Cees}, year={2017}, pages={3–17}, collection={Lecture Notes
in Computer Science} }'
chicago: 'Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Filtering
Undesirable Flows in Networks.” In Combinatorial Optimization and Applications:
11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017,
Proceedings, Part I, 3–17. Lecture Notes in Computer Science. Cham: Springer
International Publishing, 2017. https://doi.org/10.1007/978-3-319-71150-8_1.'
ieee: 'G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Filtering Undesirable
Flows in Networks,” in Combinatorial Optimization and Applications: 11th International
Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part
I, 2017, pp. 3–17.'
mla: 'Polevoy, Gleb, et al. “Filtering Undesirable Flows in Networks.” Combinatorial
Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai,
China, December 16-18, 2017, Proceedings, Part I, Springer International Publishing,
2017, pp. 3–17, doi:10.1007/978-3-319-71150-8_1.'
short: 'G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: Combinatorial Optimization
and Applications: 11th International Conference, COCOA 2017, Shanghai, China,
December 16-18, 2017, Proceedings, Part I, Springer International Publishing,
Cham, 2017, pp. 3–17.'
date_created: 2020-08-06T15:19:48Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-71150-8_1
extern: '1'
keyword:
- flow
- filter
- MMSA
- set cover
- approximation
- local ratio algorithm
language:
- iso: eng
page: 3-17
place: Cham
publication: 'Combinatorial Optimization and Applications: 11th International Conference,
COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I'
publication_identifier:
isbn:
- 978-3-319-71150-8
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Filtering Undesirable Flows in Networks
type: conference
user_id: '83983'
year: '2017'
...
---
_id: '48873'
abstract:
- lang: eng
text: Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP)
heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful
in generating satisfactory or even optimal solutions. However, the reasons for
their success are not yet fully understood. Recent approaches take an analytical
viewpoint and try to identify instance features, which make an instance hard or
easy to solve. We contribute to this area by generating instance sets for couples
of TSP algorithms A and B by maximizing/minimizing their performance difference
in order to generate instances which are easier to solve for one solver and much
harder to solve for the other. This instance set offers the potential to identify
key features which allow to distinguish between the problem hardness classes of
both algorithms.
author:
- first_name: Jakob
full_name: Bossek, Jakob
id: '102979'
last_name: Bossek
orcid: 0000-0002-4121-4668
- first_name: Heike
full_name: Trautmann, Heike
last_name: Trautmann
citation:
ama: 'Bossek J, Trautmann H. Evolving Instances for Maximizing Performance Differences
of State-of-the-Art Inexact TSP Solvers. In: Festa P, Sellmann M, Vanschoren J,
eds. Learning and Intelligent Optimization. Lecture Notes in Computer Science.
Springer International Publishing; 2016:48–59. doi:10.1007/978-3-319-50349-3_4'
apa: Bossek, J., & Trautmann, H. (2016). Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers. In P. Festa, M. Sellmann,
& J. Vanschoren (Eds.), Learning and Intelligent Optimization (pp.
48–59). Springer International Publishing. https://doi.org/10.1007/978-3-319-50349-3_4
bibtex: '@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes
in Computer Science}, title={Evolving Instances for Maximizing Performance Differences
of State-of-the-Art Inexact TSP Solvers}, DOI={10.1007/978-3-319-50349-3_4},
booktitle={Learning and Intelligent Optimization}, publisher={Springer International
Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Festa, Paola
and Sellmann, Meinolf and Vanschoren, Joaquin}, year={2016}, pages={48–59}, collection={Lecture
Notes in Computer Science} }'
chicago: 'Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing
Performance Differences of State-of-the-Art Inexact TSP Solvers.” In Learning
and Intelligent Optimization, edited by Paola Festa, Meinolf Sellmann, and
Joaquin Vanschoren, 48–59. Lecture Notes in Computer Science. Cham: Springer International
Publishing, 2016. https://doi.org/10.1007/978-3-319-50349-3_4.'
ieee: 'J. Bossek and H. Trautmann, “Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers,” in Learning and Intelligent
Optimization, 2016, pp. 48–59, doi: 10.1007/978-3-319-50349-3_4.'
mla: Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance
Differences of State-of-the-Art Inexact TSP Solvers.” Learning and Intelligent
Optimization, edited by Paola Festa et al., Springer International Publishing,
2016, pp. 48–59, doi:10.1007/978-3-319-50349-3_4.
short: 'J. Bossek, H. Trautmann, in: P. Festa, M. Sellmann, J. Vanschoren (Eds.),
Learning and Intelligent Optimization, Springer International Publishing, Cham,
2016, pp. 48–59.'
date_created: 2023-11-14T15:58:57Z
date_updated: 2023-12-13T10:47:05Z
department:
- _id: '819'
doi: 10.1007/978-3-319-50349-3_4
editor:
- first_name: Paola
full_name: Festa, Paola
last_name: Festa
- first_name: Meinolf
full_name: Sellmann, Meinolf
last_name: Sellmann
- first_name: Joaquin
full_name: Vanschoren, Joaquin
last_name: Vanschoren
extern: '1'
keyword:
- Algorithm selection
- Feature selection
- Instance hardness
- TSP
language:
- iso: eng
page: 48–59
place: Cham
publication: Learning and Intelligent Optimization
publication_identifier:
isbn:
- 978-3-319-50349-3
publication_status: published
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Evolving Instances for Maximizing Performance Differences of State-of-the-Art
Inexact TSP Solvers
type: conference
user_id: '102979'
year: '2016'
...