[{"publication":"28th International Conference on Principles of Distributed Systems (OPODIS 2024)","abstract":[{"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).","lang":"eng"}],"date_created":"2024-10-01T13:29:43Z","type":"conference","keyword":["Swarm Algorithm","Swarm Robots","Distributed Algorithm","Pattern Formation","Limited Visibility","Oblivious"],"department":[{"_id":"101"}],"year":"2025","title":"Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility","author":[{"id":"32655","full_name":"Gerlach, Raphael","orcid":"0009-0002-4750-2051","first_name":"Raphael","last_name":"Gerlach"},{"full_name":"von der Gracht, Sören","first_name":"Sören","last_name":"von der Gracht","orcid":"0000-0002-8054-2058","id":"97359"},{"full_name":"Hahn, Christopher","first_name":"Christopher","last_name":"Hahn"},{"full_name":"Harbig, Jonas","last_name":"Harbig","first_name":"Jonas","id":"47213"},{"full_name":"Kling, Peter","last_name":"Kling","first_name":"Peter"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-360-7"]},"date_updated":"2025-01-09T11:39:19Z","publication_status":"published","intvolume":" 324","main_file_link":[{"url":"https://arxiv.org/abs/2409.19277","open_access":"1"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.OPODIS.2024.13","citation":{"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","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.","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.","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.","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.","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","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)} }"},"project":[{"grant_number":"453112019","_id":"106","name":"Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme"}],"external_id":{"arxiv":["2409.19277"]},"oa":"1","status":"public","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"},"_id":"56298","publisher":"Schloss Dagstuhl -- Leibniz-Zentrum für Informatik","user_id":"97359","editor":[{"full_name":"Bonomi, Silvia","last_name":"Bonomi","first_name":"Silvia"},{"first_name":"Letterio","last_name":"Galletta","full_name":"Galletta, Letterio"},{"full_name":"Rivière, Etienne","first_name":" Etienne","last_name":"Rivière"},{"first_name":" Valerio","last_name":"Schiavoni","full_name":"Schiavoni, Valerio"}],"volume":324},{"publication":"Frontiers in Behavioral Economics","citation":{"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.","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} }","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","short":"M. Protte, B.M. Djawadi, Frontiers in Behavioral Economics 4 (2025) 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."},"type":"journal_article","keyword":["cheating","human-machine interaction","ambiguity","verification process","algorithm aversion","algorithm appreciation"],"oa":"1","date_created":"2025-09-18T07:52:40Z","date_updated":"2025-09-29T09:31:38Z","intvolume":" 4","title":"Human vs. Algorithmic Auditors: The Impact of Entity Type and Ambiguity on Human Dishonesty","status":"public","year":"2025","author":[{"id":"44549","first_name":"Marius","last_name":"Protte","full_name":"Protte, Marius"},{"first_name":"Behnud Mir","last_name":"Djawadi","full_name":"Djawadi, Behnud Mir"}],"user_id":"44549","doi":"10.3389/frbhe.2025.1645749","volume":4,"page":"1645749","main_file_link":[{"open_access":"1","url":"https://www.frontiersin.org/journals/behavioral-economics/articles/10.3389/frbhe.2025.1645749/full"}],"language":[{"iso":"eng"}],"_id":"61339"},{"type":"journal_article","keyword":["Optimization","Evolutionary computation","Benchmark testing","Hyperparameter optimization","Portfolios","Extraterrestrial measurements","Dispersion","Exploratory landscape analysis","mixed-variable problem","mixed search spaces","automated algorithm selection"],"department":[{"_id":"819"}],"date_created":"2024-06-03T06:16:33Z","publication":"IEEE Transactions on Evolutionary Computation","citation":{"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.","short":"R.P. Prager, H. Trautmann, IEEE Transactions on Evolutionary Computation (2024) 1–1.","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.","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} }","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","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."},"user_id":"15504","doi":"10.1109/TEVC.2024.3399560","page":"1-1","_id":"54548","language":[{"iso":"eng"}],"date_updated":"2024-06-03T06:17:13Z","status":"public","year":"2024","title":"Exploratory Landscape Analysis for Mixed-Variable Problems","author":[{"last_name":"Prager","first_name":"Raphael Patrick","full_name":"Prager, Raphael Patrick"},{"last_name":"Trautmann","orcid":"0000-0002-9788-8282","first_name":"Heike","full_name":"Trautmann, Heike","id":"100740"}]},{"date_updated":"2024-01-10T09:52:59Z","author":[{"orcid":"0000-0001-9004-2391","first_name":"Dirk","last_name":"Leffrang","full_name":"Leffrang, Dirk","id":"51271"},{"first_name":"Kevin","last_name":"Bösch","full_name":"Bösch, Kevin"},{"id":"72849","full_name":"Müller, Oliver","first_name":"Oliver","last_name":"Müller"}],"conference":{"name":"Hawaii International Conference on System Sciences"},"year":"2023","status":"public","title":"Do People Recover from Algorithm Aversion? An Experimental Study of Algorithm Aversion over Time","user_id":"51271","_id":"37312","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://scholarspace.manoa.hawaii.edu/items/62b58ddc-895c-48c3-8194-522a1758a26f"}],"abstract":[{"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.","lang":"eng"}],"citation":{"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} }","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.","short":"D. Leffrang, K. Bösch, O. Müller, in: Hawaii International Conference on System Sciences, 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.","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."},"publication":"Hawaii International Conference on System Sciences","department":[{"_id":"196"}],"oa":"1","type":"conference","keyword":["Algorithm aversion","Time series","Decision making","Advice taking","Forecasting"],"date_created":"2023-01-18T10:53:51Z"},{"user_id":"51271","_id":"50121","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://aisel.aisnet.org/icis2023/aiinbus/aiinbus/10"}],"date_updated":"2024-01-10T09:53:41Z","author":[{"id":"51271","full_name":"Leffrang, Dirk","first_name":"Dirk","orcid":"0000-0001-9004-2391","last_name":"Leffrang"}],"conference":{"location":"Hyderabad, India","name":"International Conference on Information Systems (ICIS)"},"title":"AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization","year":"2023","status":"public","department":[{"_id":"196"}],"keyword":["Artificial Intelligence","Algorithm Appreciation","Framing","Advice-taking","Expertise"],"type":"conference","date_created":"2024-01-03T09:54:00Z","abstract":[{"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.","lang":"eng"}],"citation":{"chicago":"Leffrang, Dirk. “AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization.” In International Conference on Information Systems, 2023.","ama":"Leffrang D. AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization. In: International Conference on Information Systems. ; 2023.","short":"D. Leffrang, in: International Conference on Information Systems, 2023.","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} }","mla":"Leffrang, Dirk. “AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization.” International Conference on Information Systems, no. 10, 2023.","apa":"Leffrang, D. (2023). AI Washing: The Framing Effect of Labels on Algorithmic Advice Utilization. International Conference on Information Systems, 10.","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."},"publication":"International Conference on Information Systems","issue":"10"},{"status":"public","title":"The Broken Leg of Algorithm Appreciation: An Experimental Study on the Effect of Unobserved Variables on Advice Utilization","year":"2023","author":[{"full_name":"Leffrang, Dirk","first_name":"Dirk","orcid":"0000-0001-9004-2391","last_name":"Leffrang","id":"51271"}],"conference":{"name":"Wirtschaftsinformatik","location":"Paderborn"},"date_updated":"2024-01-10T09:53:24Z","main_file_link":[{"url":"https://aisel.aisnet.org/wi2023/19 "}],"_id":"50118","language":[{"iso":"eng"}],"user_id":"51271","issue":"19","publication":"Wirtschaftsinformatik Conference","citation":{"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.","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.","short":"D. Leffrang, in: Wirtschaftsinformatik Conference, 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.","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.","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.","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} }"},"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."}],"date_created":"2024-01-03T09:50:06Z","type":"conference","keyword":["Algorithm aversion","Data","Decision-making","Advice-taking","Human-Computer Interaction"],"department":[{"_id":"196"}]},{"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."}],"citation":{"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.","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","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} }","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","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.","short":"J. Heins, J. Bossek, J. Pohl, M. Seiler, H. Trautmann, P. Kerschke, Theoretical Computer Science 940 (2023) 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."},"publication":"Theoretical Computer Science","department":[{"_id":"34"},{"_id":"819"}],"keyword":["Feature normalization","Algorithm selection","Traveling salesperson problem"],"type":"journal_article","date_created":"2023-08-04T07:18:38Z","intvolume":" 940","date_updated":"2024-06-10T11:57:21Z","publication_identifier":{"issn":["0304-3975"]},"author":[{"full_name":"Heins, Jonathan","last_name":"Heins","first_name":"Jonathan"},{"orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979"},{"last_name":"Pohl","first_name":"Janina","full_name":"Pohl, Janina"},{"id":"105520","full_name":"Seiler, Moritz","last_name":"Seiler","first_name":"Moritz"},{"id":"100740","first_name":"Heike","orcid":"0000-0002-9788-8282","last_name":"Trautmann","full_name":"Trautmann, Heike"},{"full_name":"Kerschke, Pascal","last_name":"Kerschke","first_name":"Pascal"}],"year":"2023","title":"A study on the effects of normalized TSP features for automated algorithm selection","status":"public","volume":940,"doi":"https://doi.org/10.1016/j.tcs.2022.10.019","user_id":"15504","language":[{"iso":"eng"}],"_id":"46310","page":"123-145"},{"language":[{"iso":"ger"}],"date_updated":"2024-07-31T07:51:08Z","publication_status":"published","author":[{"id":"7117","first_name":"Swen","last_name":"Schulte Eickholt","full_name":"Schulte Eickholt, Swen"}],"year":"2023","title":"Normative Diversität? Nahe Zukunft bei Sibylle Berg und Marc-Uwe Kling","department":[{"_id":"465"}],"type":"book_chapter","keyword":["diversity","normality","contemporary literature","algorithm","distopia","Diversität","Normalität","Gegenwartsliteratur","Algorithmus","Dystopie"],"date_created":"2024-05-23T09:25:19Z","abstract":[{"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.","lang":"eng"}],"publication":"Germanistik im Wandel 1. Neue Einsichten und Perspektiven in der Literaturwissenschaft","editor":[{"full_name":"Cosan, Leyla","last_name":"Cosan","first_name":"Leyla"},{"first_name":"Onur Kemal","last_name":"Bazarkaya","full_name":"Bazarkaya, Onur Kemal"},{"last_name":"Tekin","first_name":"Habib","full_name":"Tekin, Habib"}],"user_id":"7117","_id":"54428","publisher":"Logos","page":"65-75","status":"public","place":"Berlin","quality_controlled":"1","citation":{"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.","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.","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.","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.","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.","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} }","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."}},{"page":"1–15","language":[{"iso":"eng"}],"_id":"48881","publisher":"Association for Computing Machinery","user_id":"102979","year":"2021","status":"public","title":"On the Potential of Normalized TSP Features for Automated Algorithm Selection","publication_identifier":{"isbn":["978-1-4503-8352-3"]},"author":[{"full_name":"Heins, Jonathan","last_name":"Heins","first_name":"Jonathan"},{"id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob","full_name":"Bossek, Jakob"},{"full_name":"Pohl, Janina","last_name":"Pohl","first_name":"Janina"},{"first_name":"Moritz","last_name":"Seiler","full_name":"Seiler, Moritz"},{"last_name":"Trautmann","first_name":"Heike","full_name":"Trautmann, Heike"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"}],"date_updated":"2023-12-13T10:47:23Z","place":"New York, NY, USA","date_created":"2023-11-14T15:58:58Z","type":"book_chapter","keyword":["automated algorithm selection","graph theory","instance features","normalization","traveling salesperson problem (TSP)"],"department":[{"_id":"819"}],"publication":"Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","citation":{"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.","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.","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} }","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.","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.","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.","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."},"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."}],"extern":"1"},{"_id":"48897","publisher":"Springer-Verlag","page":"48–64","user_id":"102979","status":"public","place":"Berlin, Heidelberg","citation":{"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.","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","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.","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.","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.","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"},"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-58112-1_4","publication_identifier":{"isbn":["978-3-030-58111-4"]},"author":[{"last_name":"Seiler","first_name":"Moritz","full_name":"Seiler, Moritz"},{"last_name":"Pohl","first_name":"Janina","full_name":"Pohl, Janina"},{"id":"102979","last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"last_name":"Trautmann","first_name":"Heike","full_name":"Trautmann, Heike"}],"title":"Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem","year":"2020","date_updated":"2023-12-13T10:49:45Z","date_created":"2023-11-14T15:59:00Z","department":[{"_id":"819"}],"type":"conference","keyword":["Automated algorithm selection","Deep learning","Feature-based approaches","Traveling Salesperson Problem"],"publication":"Parallel Problem Solving from {Nature} (PPSN XVI)","extern":"1","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."}]},{"citation":{"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.","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","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.","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.","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","short":"J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020)."},"issue":"C","publication":"Applied Soft Computing","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."}],"date_created":"2023-11-14T15:58:53Z","department":[{"_id":"819"}],"keyword":["Algorithm selection","Combinatorial optimization","Multi-objective optimization","Performance measurement","Traveling Salesperson Problem"],"type":"journal_article","author":[{"id":"102979","last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"full_name":"Trautmann, Heike","first_name":"Heike","last_name":"Trautmann"}],"publication_identifier":{"issn":["1568-4946"]},"title":"A Multi-Objective Perspective on Performance Assessment and Automated Selection of Single-Objective Optimization Algorithms","status":"public","year":"2020","intvolume":" 88","date_updated":"2023-12-13T10:52:17Z","_id":"48848","language":[{"iso":"eng"}],"volume":88,"user_id":"102979","doi":"10.1016/j.asoc.2019.105901"},{"date_updated":"2024-06-10T12:00:46Z","intvolume":" 88","status":"public","year":"2020","title":"A multi-objective perspective on performance assessment and automated selection of single-objective optimization algorithms","publication_identifier":{"issn":["1568-4946"]},"author":[{"id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"full_name":"Kerschke, Pascal","first_name":"Pascal","last_name":"Kerschke"},{"orcid":"0000-0002-9788-8282","last_name":"Trautmann","first_name":"Heike","full_name":"Trautmann, Heike","id":"100740"}],"user_id":"15504","doi":"https://doi.org/10.1016/j.asoc.2019.105901","volume":88,"page":"105901","language":[{"iso":"eng"}],"_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."}],"publication":"Applied Soft Computing","citation":{"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.","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} }","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","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.","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","short":"J. Bossek, P. Kerschke, H. Trautmann, Applied Soft Computing 88 (2020) 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."},"keyword":["Algorithm selection","Multi-objective optimization","Performance measurement","Combinatorial optimization","Traveling Salesperson Problem"],"type":"journal_article","department":[{"_id":"34"},{"_id":"819"}],"date_created":"2023-08-04T07:42:26Z"},{"language":[{"iso":"eng"}],"date_updated":"2022-01-06T07:03:08Z","author":[{"first_name":"Gerhard","last_name":"Rauchecker","full_name":"Rauchecker, Gerhard"},{"id":"72850","full_name":"Schryen, Guido","last_name":"Schryen","first_name":"Guido"}],"year":"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","department":[{"_id":"277"}],"keyword":["parallel machine scheduling with setup times","parallel branch-and-price algorithm","high performance computing","master/worker parallelization"],"type":"journal_article","date_created":"2019-01-08T13:50:44Z","file":[{"file_id":"6513","content_type":"application/pdf","relation":"main_file","date_updated":"2019-01-08T14:03:53Z","file_name":"cor-parallel-bp-for-upmsp.pdf","file_size":4153528,"access_level":"open_access","date_created":"2019-01-08T14:03:53Z","creator":"hsiemes"}],"abstract":[{"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.","lang":"eng"}],"publication":"Computers & Operations Research","issue":"104","user_id":"61579","ddc":["000"],"_id":"6512","publisher":"Elsevier","page":"338-357","has_accepted_license":"1","status":"public","oa":"1","citation":{"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.","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.","short":"G. Rauchecker, G. Schryen, Computers & Operations Research (2019) 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.","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.","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.","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} }"},"file_date_updated":"2019-01-08T14:03:53Z"},{"department":[{"_id":"819"}],"type":"conference","keyword":["Algorithm selection","Performance measurement"],"date_created":"2023-11-14T15:58:57Z","extern":"1","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."}],"publication":"Learning and Intelligent Optimization","doi":"10.1007/978-3-030-05348-2_19","language":[{"iso":"eng"}],"series_title":"Lecture Notes in Computer Science","date_updated":"2023-12-13T10:47:32Z","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979"},{"last_name":"Trautmann","first_name":"Heike","full_name":"Trautmann, Heike"}],"publication_identifier":{"isbn":["978-3-030-05348-2"]},"title":"Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time","year":"2019","place":"Cham","citation":{"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.","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","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.","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.","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","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."},"editor":[{"last_name":"Battiti","first_name":"Roberto","full_name":"Battiti, Roberto"},{"last_name":"Brunato","first_name":"Mauro","full_name":"Brunato, Mauro"},{"full_name":"Kotsireas, Ilias","last_name":"Kotsireas","first_name":"Ilias"},{"full_name":"Pardalos, Panos M.","last_name":"Pardalos","first_name":"Panos M."}],"user_id":"102979","publisher":"Springer International Publishing","_id":"48875","page":"215–219","status":"public"},{"date_updated":"2022-01-06T06:59:16Z","publication_status":"accepted","title":"Breaking the $\\tilde\\Omega(\\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary","year":"2018","publication_identifier":{"isbn":["978-1-4503-5799-9/18/07"]},"author":[{"last_name":"Robinson","first_name":"Peter","full_name":"Robinson, Peter"},{"id":"20792","full_name":"Scheideler, Christian","first_name":"Christian","last_name":"Scheideler"},{"first_name":"Alexander","last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108"}],"doi":"10.1145/3210377.3210399","language":[{"iso":"eng"}],"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."}],"publication":"Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","type":"conference","keyword":["distributed consensus","randomized algorithm","adaptive adversary","complexity lower bound"],"department":[{"_id":"79"},{"_id":"34"},{"_id":"7"}],"file":[{"file_id":"5215","success":1,"content_type":"application/pdf","file_name":"p173-robinson.pdf","access_level":"closed","file_size":1675407,"relation":"main_file","date_updated":"2018-10-31T13:30:40Z","date_created":"2018-10-31T13:30:40Z","creator":"asetzer"}],"date_created":"2018-07-04T08:55:45Z","has_accepted_license":"1","status":"public","conference":{"end_date":"2018-07-18","name":"30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","start_date":"2018-07-16","location":"Wien"},"ddc":["040"],"user_id":"11108","_id":"3422","project":[{"name":"SFB 901","_id":"1"},{"_id":"4","name":"SFB 901 - Project Area C"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"file_date_updated":"2018-10-31T13:30:40Z","citation":{"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.","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","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} }","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","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.","short":"P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), n.d.","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."}},{"citation":{"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.","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","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} }","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","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.","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.","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."},"place":"New York, NY, USA","status":"public","user_id":"102979","page":"1737–1744","publisher":"Association for Computing Machinery","_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."}],"extern":"1","publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","keyword":["algorithm selection","optimization","performance measures","transportation","travelling salesperson problem"],"type":"conference","department":[{"_id":"819"}],"date_created":"2023-11-14T15:58:59Z","date_updated":"2023-12-13T10:48:38Z","title":"Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers","year":"2018","author":[{"full_name":"Kerschke, Pascal","last_name":"Kerschke","first_name":"Pascal"},{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979"},{"full_name":"Trautmann, Heike","first_name":"Heike","last_name":"Trautmann"}],"publication_identifier":{"isbn":["978-1-4503-5764-7"]},"doi":"10.1145/3205651.3208233","language":[{"iso":"eng"}],"series_title":"GECCO’18"},{"status":"public","_id":"48884","page":"597–620","volume":26,"user_id":"102979","citation":{"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.","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} }","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","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.","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","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.","short":"P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary Computation 26 (2018) 597–620."},"author":[{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"first_name":"Lars","last_name":"Kotthoff","full_name":"Kotthoff, Lars"},{"full_name":"Bossek, Jakob","first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979"},{"last_name":"Hoos","first_name":"Holger H.","full_name":"Hoos, Holger H."},{"first_name":"Heike","last_name":"Trautmann","full_name":"Trautmann, Heike"}],"publication_identifier":{"issn":["1063-6560"]},"title":"Leveraging TSP Solver Complementarity through Machine Learning","year":"2018","intvolume":" 26","date_updated":"2023-12-13T10:51:26Z","language":[{"iso":"eng"}],"doi":"10.1162/evco_a_00215","issue":"4","publication":"Evolutionary Computation","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."}],"date_created":"2023-11-14T15:58:58Z","department":[{"_id":"819"}],"keyword":["automated algorithm selection","machine learning.","performance modeling","Travelling Salesperson Problem"],"type":"journal_article"},{"author":[{"id":"24135","full_name":"Lass, Michael","orcid":"0000-0002-5708-7632","first_name":"Michael","last_name":"Lass"},{"first_name":"Stephan","last_name":"Mohr","full_name":"Mohr, Stephan"},{"full_name":"Wiebeler, Hendrik","first_name":"Hendrik","last_name":"Wiebeler"},{"first_name":"Thomas","last_name":"Kühne","full_name":"Kühne, Thomas","id":"49079"},{"orcid":"0000-0001-5728-9982","last_name":"Plessl","first_name":"Christian","full_name":"Plessl, Christian","id":"16153"}],"publication_identifier":{"isbn":["978-1-4503-5891-0/18/07"]},"year":"2018","title":"A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices","date_updated":"2023-09-26T11:48:12Z","language":[{"iso":"eng"}],"doi":"10.1145/3218176.3218231","publication":"Proc. Platform for Advanced Scientific Computing (PASC) Conference","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."}],"date_created":"2018-03-22T10:53:01Z","department":[{"_id":"27"},{"_id":"518"},{"_id":"304"}],"keyword":["approximate computing","linear algebra","matrix inversion","matrix p-th roots","numeric algorithm","parallel computing"],"type":"conference","conference":{"start_date":"2018-07-02","name":"Platform for Advanced Scientific Computing Conference (PASC)","location":"Basel, Switzerland","end_date":"2018-07-04"},"status":"public","publisher":"ACM","_id":"1590","user_id":"15278","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","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} }","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.","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.","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.","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","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."},"project":[{"name":"Performance and Efficiency in HPC with Custom Computing","_id":"32","grant_number":"PL 595/2-1 / 320898746"},{"_id":"52","name":"Computing Resources Provided by the Paderborn Center for Parallel Computing"}],"quality_controlled":"1","place":"New York, NY, USA","external_id":{"arxiv":["1710.10899"]}},{"status":"public","user_id":"83983","page":"3-17","_id":"17652","publisher":"Springer International Publishing","citation":{"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.","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} }","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","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.","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."},"place":"Cham","date_updated":"2022-01-06T06:53:16Z","year":"2017","title":"Filtering Undesirable Flows in Networks","publication_identifier":{"isbn":["978-3-319-71150-8"]},"author":[{"full_name":"Polevoy, Gleb","first_name":"Gleb","last_name":"Polevoy","id":"83983"},{"last_name":"Trajanovski","first_name":"Stojan","full_name":"Trajanovski, Stojan"},{"first_name":"Paola","last_name":"Grosso","full_name":"Grosso, Paola"},{"last_name":"de Laat","first_name":"Cees","full_name":"de Laat, Cees"}],"doi":"10.1007/978-3-319-71150-8_1","series_title":"Lecture Notes in Computer Science","language":[{"iso":"eng"}],"extern":"1","publication":"Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I","keyword":["flow","filter","MMSA","set cover","approximation","local ratio algorithm"],"type":"conference","department":[{"_id":"63"},{"_id":"541"}],"date_created":"2020-08-06T15:19:48Z"},{"citation":{"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} }","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","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.","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.","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"},"place":"Cham","status":"public","publisher":"Springer International Publishing","_id":"48873","page":"48–59","editor":[{"last_name":"Festa","first_name":"Paola","full_name":"Festa, Paola"},{"full_name":"Sellmann, Meinolf","first_name":"Meinolf","last_name":"Sellmann"},{"last_name":"Vanschoren","first_name":"Joaquin","full_name":"Vanschoren, Joaquin"}],"user_id":"102979","publication":"Learning and Intelligent Optimization","extern":"1","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."}],"date_created":"2023-11-14T15:58:57Z","department":[{"_id":"819"}],"type":"conference","keyword":["Algorithm selection","Feature selection","Instance hardness","TSP"],"author":[{"last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979"},{"full_name":"Trautmann, Heike","first_name":"Heike","last_name":"Trautmann"}],"publication_identifier":{"isbn":["978-3-319-50349-3"]},"title":"Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers","year":"2016","publication_status":"published","date_updated":"2023-12-13T10:47:05Z","series_title":"Lecture Notes in Computer Science","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-50349-3_4"}]