TY - BOOK A1 - Zhang, Shuhao A1 - Plauth, Max A1 - Eberhardt, Felix A1 - Polze, Andreas A1 - Lehmann, Jens A1 - Sejdiu, Gezim A1 - Jabeen, Hajira A1 - Servadei, Lorenzo A1 - Möstl, Christian A1 - Bär, Florian A1 - Netzeband, André A1 - Schmidt, Rainer A1 - Knigge, Marlene A1 - Hecht, Sonja A1 - Prifti, Loina A1 - Krcmar, Helmut A1 - Sapegin, Andrey A1 - Jaeger, David A1 - Cheng, Feng A1 - Meinel, Christoph A1 - Friedrich, Tobias A1 - Rothenberger, Ralf A1 - Sutton, Andrew M. A1 - Sidorova, Julia A. A1 - Lundberg, Lars A1 - Rosander, Oliver A1 - Sköld, Lars A1 - Di Varano, Igor A1 - van der Walt, Estée A1 - Eloff, Jan H. P. A1 - Fabian, Benjamin A1 - Baumann, Annika A1 - Ermakova, Tatiana A1 - Kelkel, Stefan A1 - Choudhary, Yash A1 - Cooray, Thilini A1 - Rodríguez, Jorge A1 - Medina-Pérez, Miguel Angel A1 - Trejo, Luis A. A1 - Barrera-Animas, Ari Yair A1 - Monroy-Borja, Raúl A1 - López-Cuevas, Armando A1 - Ramírez-Márquez, José Emmanuel A1 - Grohmann, Maria A1 - Niederleithinger, Ernst A1 - Podapati, Sasidhar A1 - Schmidt, Christopher A1 - Huegle, Johannes A1 - de Oliveira, Roberto C. L. A1 - Soares, Fábio Mendes A1 - van Hoorn, André A1 - Neumer, Tamas A1 - Willnecker, Felix A1 - Wilhelm, Mathias A1 - Kuster, Bernhard ED - Meinel, Christoph ED - Polze, Andreas ED - Beins, Karsten ED - Strotmann, Rolf ED - Seibold, Ulrich ED - Rödszus, Kurt ED - Müller, Jürgen T1 - HPI Future SOC Lab – Proceedings 2017 T1 - HPI Future SOC Lab – Proceedings 2017 N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners. The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies. This technical report presents results of research projects executed in 2017. Selected projects have presented their results on April 25th and November 15th 2017 at the Future SOC Lab Day events. N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie. Am Lab wird interessierten Wissenschaftlern eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen teilweise noch nicht am Markt verfügbare Technologien, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien. In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2017 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 25. April und 15. November 2017 im Rahmen der Future SOC Lab Tag Veranstaltungen vor. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 130 KW - Future SOC Lab KW - research projects KW - multicore architectures KW - In-Memory technology KW - cloud computing KW - machine learning KW - artifical intelligence KW - Future SOC Lab KW - Forschungsprojekte KW - Multicore Architekturen KW - In-Memory Technologie KW - Cloud Computing KW - maschinelles Lernen KW - Künstliche Intelligenz Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-433100 SN - 978-3-86956-475-3 SN - 1613-5652 SN - 2191-1665 IS - 130 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Shi, Feng A1 - Schirneck, Friedrich Martin A1 - Friedrich, Tobias A1 - Kötzing, Timo A1 - Neumann, Frank T1 - Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints JF - Algorithmica : an international journal in computer science N2 - Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ))GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-605295 SN - 0178-4617 SN - 1432-0541 VL - 82 IS - 10 SP - 3117 EP - 3123 PB - Springer CY - New York ER - TY - BOOK A1 - Schwarzer, Ingo A1 - Weiß-Saoumi, Said A1 - Kittel, Roland A1 - Friedrich, Tobias A1 - Kaynak, Koraltan A1 - Durak, Cemil A1 - Isbarn, Andreas A1 - Diestel, Jörg A1 - Knittel, Jens A1 - Franz, Marquart A1 - Morra, Carlos A1 - Stahnke, Susanne A1 - Braband, Jens A1 - Dittmann, Johannes A1 - Griebel, Stephan A1 - Krampf, Andreas A1 - Link, Martin A1 - Müller, Matthias A1 - Radestock, Jens A1 - Strub, Leo A1 - Bleeke, Kai A1 - Jehl, Leander A1 - Kapitza, Rüdiger A1 - Messadi, Ines A1 - Schmidt, Stefan A1 - Schwarz-Rüsch, Signe A1 - Pirl, Lukas A1 - Schmid, Robert A1 - Friedenberger, Dirk A1 - Beilharz, Jossekin Jakob A1 - Boockmeyer, Arne A1 - Polze, Andreas A1 - Röhrig, Ralf A1 - Schäbe, Hendrik A1 - Thiermann, Ricky T1 - RailChain BT - Abschlussbericht N2 - The RailChain project designed, implemented, and experimentally evaluated a juridical recorder that is based on a distributed consensus protocol. That juridical blockchain recorder has been realized as distributed ledger on board the advanced TrainLab (ICE-TD 605 017) of Deutsche Bahn. For the project, a consortium consisting of DB Systel, Siemens, Siemens Mobility, the Hasso Plattner Institute for Digital Engineering, Technische Universität Braunschweig, TÜV Rheinland InterTraffic, and Spherity has been formed. These partners not only concentrated competencies in railway operation, computer science, regulation, and approval, but also combined experiences from industry, research from academia, and enthusiasm from startups. Distributed ledger technologies (DLTs) define distributed databases and express a digital protocol for transactions between business partners without the need for a trusted intermediary. The implementation of a blockchain with real-time requirements for the local network of a railway system (e.g., interlocking or train) allows to log data in the distributed system verifiably in real-time. For this, railway-specific assumptions can be leveraged to make modifications to standard blockchains protocols. EULYNX and OCORA (Open CCS On-board Reference Architecture) are parts of a future European reference architecture for control command and signalling (CCS, Reference CCS Architecture – RCA). Both architectural concepts outline heterogeneous IT systems with components from multiple manufacturers. Such systems introduce novel challenges for the approved and safety-relevant CCS of railways which were considered neither for road-side nor for on-board systems so far. Logging implementations, such as the common juridical recorder on vehicles, can no longer be realized as a central component of a single manufacturer. All centralized approaches are in question. The research project RailChain is funded by the mFUND program and gives practical evidence that distributed consensus protocols are a proper means to immutably (for legal purposes) store state information of many system components from multiple manufacturers. The results of RailChain have been published, prototypically implemented, and experimentally evaluated in large-scale field tests on the advanced TrainLab. At the same time, the project showed how RailChain can be integrated into the road-side and on-board architecture given by OCORA and EULYNX. Logged data can now be analysed sooner and also their trustworthiness is being increased. This enables, e.g., auditable predictive maintenance, because it is ensured that data is authentic and unmodified at any point in time. N2 - Das Projekt RailChain hat einen verteilten Juridical Recorder entworfen, implementiert und experimentell evaluiert, der auf einem echtzeitfähigen verteilten Konsensprotokoll basiert. Dieser Juridical Blockchain Recorder wurde als distributed ledger an Bord des advanced TrainLabs der Deutschen Bahn (ICE-TD 605 017) umgesetzt. Für das Projekt hat sich ein Konsortium aus DB Systel, Siemens, Siemens Mobility, dem Hasso-Plattner-Institut für Digital Engineering, der Technischen Universität Braunschweig, sowie TÜV Rheinland InterTraffic und Spherity formiert und dabei Kompetenzen aus den Bereichen Bahnbetrieb, Informatik und Zulassungswesen gebündelt. Die Partner kombinieren Erfahrungen aus der Industrie und die akademische Forschung mit der Aufbruchstimmung aus dem Start-Up-Umfeld. Distributed-Ledger-Technologien (DLTs) definieren verteilte Datenbanken und stellen ein digitales Protokoll für Transaktionen zwischen Geschäftspartnern dar, ohne dass ein Mittelsmann beteiligt sein müsste. Die Implementierung einer Blockchain mit Echtzeitanforderungen für das lokale Netzwerk einer Eisenbahnanlage (z. B. Stellwerk oder Zug) erlaubt es, die im verteilten System entstehenden Daten nachweislich in Echtzeit zu protokollieren. Dabei können eisenbahnspezifische Randbedingungen ausgenutzt werden, um Standard-Blockchain-Protokolle anzupassen. EULYNX und OCORA (Open CCS On-board Reference Architecture) sind Bestandteile einer zukünftigen europäischen Referenzarchitektur für das Leit- und Sicherungssystem (Reference CCS Architecture – RCA, Control Command and Signalling – CCS). Beide Architekturkonzepte skizzieren herstellerübergreifende, komponentenbasierende heterogene IT-Systeme. Solche Systeme bergen neue Herausforderungen, die bislang im Kontext der zugelassenen, sicherheitsrelevanten Leit- und Sicherungstechnik der Bahn weder strecken- noch fahrzeugseitig adressiert werden mussten. Logbuch-Implementierungen, wie der gängige Juridical Recorder auf Fahrzeugen, können nun nicht mehr als zentrale Systemkomponente eines einzelnen Herstellers umgesetzt werden. Alle zentralisierten Lösungsansätze sind in Frage gestellt. Das mFUND-geförderte Forschungsprojekt erbringt den praktischen Nachweis, dass Zustandsinformationen über eine Vielzahl von Systemkomponenten herstellerübergreifend und gerichtsfest mittels verteilten Konsensprotokollen gespeichert werden können. Ergebnisse von RailChain wurden publiziert, prototypisch implementiert und in großen Feldtests auf dem advanced TrainLab experimentell evaluiert. Gleichzeitig wurde aufgezeigt, wie sich RailChain in den mit OCORA und EULYNX vorgegebenen fahrzeug- und streckenseitigen Architekturentwurf integrieren lässt. Daten können dadurch zeitnaher ausgewertet werden und gleichzeitig wird ihre Vertrauenswürdigkeit erhöht. Dies ermöglicht u. a. nachvollziehbare zustandsorientierte Wartung, denn es kann jederzeit sichergestellt werden, dass die Daten authentisch sind und auch nicht verändert wurden. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 152 KW - Distributed-Ledger-Technologie (DLT) KW - juridical recording KW - Konsensprotokolle KW - consensus protocols KW - Digitalisierung KW - digitalization KW - Bahnwesen KW - railways KW - Blockchain KW - asset management KW - selbstbestimmte Identitäten KW - self-sovereign identity KW - dezentrale Identitäten KW - decentral identities KW - überprüfbare Nachweise KW - verifiable credentials KW - Echtzeit KW - real-time KW - Standardisierung KW - standardization KW - Verlässlichkeit KW - dependability KW - Fehlertoleranz KW - fault tolerance Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-577409 SN - 978-3-86956-550-7 SN - 1613-5652 SN - 2191-1665 IS - 152 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Rana, Kaushik A1 - Mohapatra, Durga Prasad A1 - Sidorova, Julia A1 - Lundberg, Lars A1 - Sköld, Lars A1 - Lopes Grim, Luís Fernando A1 - Sampaio Gradvohl, André Leon A1 - Cremerius, Jonas A1 - Siegert, Simon A1 - Weltzien, Anton von A1 - Baldi, Annika A1 - Klessascheck, Finn A1 - Kalancha, Svitlana A1 - Lichtenstein, Tom A1 - Shaabani, Nuhad A1 - Meinel, Christoph A1 - Friedrich, Tobias A1 - Lenzner, Pascal A1 - Schumann, David A1 - Wiese, Ingmar A1 - Sarna, Nicole A1 - Wiese, Lena A1 - Tashkandi, Araek Sami A1 - van der Walt, Estée A1 - Eloff, Jan H. P. A1 - Schmidt, Christopher A1 - Hügle, Johannes A1 - Horschig, Siegfried A1 - Uflacker, Matthias A1 - Najafi, Pejman A1 - Sapegin, Andrey A1 - Cheng, Feng A1 - Stojanovic, Dragan A1 - Stojnev Ilić, Aleksandra A1 - Djordjevic, Igor A1 - Stojanovic, Natalija A1 - Predic, Bratislav A1 - González-Jiménez, Mario A1 - de Lara, Juan A1 - Mischkewitz, Sven A1 - Kainz, Bernhard A1 - van Hoorn, André A1 - Ferme, Vincenzo A1 - Schulz, Henning A1 - Knigge, Marlene A1 - Hecht, Sonja A1 - Prifti, Loina A1 - Krcmar, Helmut A1 - Fabian, Benjamin A1 - Ermakova, Tatiana A1 - Kelkel, Stefan A1 - Baumann, Annika A1 - Morgenstern, Laura A1 - Plauth, Max A1 - Eberhard, Felix A1 - Wolff, Felix A1 - Polze, Andreas A1 - Cech, Tim A1 - Danz, Noel A1 - Noack, Nele Sina A1 - Pirl, Lukas A1 - Beilharz, Jossekin Jakob A1 - De Oliveira, Roberto C. L. A1 - Soares, Fábio Mendes A1 - Juiz, Carlos A1 - Bermejo, Belen A1 - Mühle, Alexander A1 - Grüner, Andreas A1 - Saxena, Vageesh A1 - Gayvoronskaya, Tatiana A1 - Weyand, Christopher A1 - Krause, Mirko A1 - Frank, Markus A1 - Bischoff, Sebastian A1 - Behrens, Freya A1 - Rückin, Julius A1 - Ziegler, Adrian A1 - Vogel, Thomas A1 - Tran, Chinh A1 - Moser, Irene A1 - Grunske, Lars A1 - Szárnyas, Gábor A1 - Marton, József A1 - Maginecz, János A1 - Varró, Dániel A1 - Antal, János Benjamin ED - Meinel, Christoph ED - Polze, Andreas ED - Beins, Karsten ED - Strotmann, Rolf ED - Seibold, Ulrich ED - Rödszus, Kurt ED - Müller, Jürgen T1 - HPI Future SOC Lab – Proceedings 2018 N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners. The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies. This technical report presents results of research projects executed in 2018. Selected projects have presented their results on April 17th and November 14th 2017 at the Future SOC Lab Day events. N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie. Am Lab wird interessierten Wissenschaftler:innen eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen Systeme, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler:innen in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien. In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2018 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 17. April und 14. November 2018 im Rahmen des Future SOC Lab Tags vor. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 151 KW - Future SOC Lab KW - research projects KW - multicore architectures KW - in-memory technology KW - cloud computing KW - machine learning KW - artifical intelligence KW - Future SOC Lab KW - Forschungsprojekte KW - Multicore Architekturen KW - In-Memory Technologie KW - Cloud Computing KW - maschinelles Lernen KW - künstliche Intelligenz Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-563712 SN - 978-3-86956-547-7 SN - 1613-5652 SN - 2191-1665 IS - 151 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Meinel, Christoph A1 - Döllner, Jürgen Roland Friedrich A1 - Weske, Mathias A1 - Polze, Andreas A1 - Hirschfeld, Robert A1 - Naumann, Felix A1 - Giese, Holger A1 - Baudisch, Patrick A1 - Friedrich, Tobias A1 - Böttinger, Erwin A1 - Lippert, Christoph A1 - Dörr, Christian A1 - Lehmann, Anja A1 - Renard, Bernhard A1 - Rabl, Tilmann A1 - Uebernickel, Falk A1 - Arnrich, Bert A1 - Hölzle, Katharina T1 - Proceedings of the HPI Research School on Service-oriented Systems Engineering 2020 Fall Retreat N2 - Design and Implementation of service-oriented architectures imposes a huge number of research questions from the fields of software engineering, system analysis and modeling, adaptability, and application integration. Component orientation and web services are two approaches for design and realization of complex web-based system. Both approaches allow for dynamic application adaptation as well as integration of enterprise application. Service-Oriented Systems Engineering represents a symbiosis of best practices in object-orientation, component-based development, distributed computing, and business process management. It provides integration of business and IT concerns. The annual Ph.D. Retreat of the Research School provides each member the opportunity to present his/her current state of their research and to give an outline of a prospective Ph.D. thesis. Due to the interdisciplinary structure of the research school, this technical report covers a wide range of topics. These include but are not limited to: Human Computer Interaction and Computer Vision as Service; Service-oriented Geovisualization Systems; Algorithm Engineering for Service-oriented Systems; Modeling and Verification of Self-adaptive Service-oriented Systems; Tools and Methods for Software Engineering in Service-oriented Systems; Security Engineering of Service-based IT Systems; Service-oriented Information Systems; Evolutionary Transition of Enterprise Applications to Service Orientation; Operating System Abstractions for Service-oriented Computing; and Services Specification, Composition, and Enactment. N2 - Der Entwurf und die Realisierung dienstbasierender Architekturen wirft eine Vielzahl von Forschungsfragestellungen aus den Gebieten der Softwaretechnik, der Systemmodellierung und -analyse, sowie der Adaptierbarkeit und Integration von Applikationen auf. Komponentenorientierung und WebServices sind zwei Ansätze für den effizienten Entwurf und die Realisierung komplexer Web-basierender Systeme. Sie ermöglichen die Reaktion auf wechselnde Anforderungen ebenso, wie die Integration großer komplexer Softwaresysteme. "Service-Oriented Systems Engineering" repräsentiert die Symbiose bewährter Praktiken aus den Gebieten der Objektorientierung, der Komponentenprogrammierung, des verteilten Rechnen sowie der Geschäftsprozesse und berücksichtigt auch die Integration von Geschäftsanliegen und Informationstechnologien. Die Klausurtagung des Forschungskollegs "Service-oriented Systems Engineering" findet einmal jährlich statt und bietet allen Kollegiaten die Möglichkeit den Stand ihrer aktuellen Forschung darzulegen. Bedingt durch die Querschnittstruktur des Kollegs deckt dieser Bericht ein weites Spektrum aktueller Forschungsthemen ab. Dazu zählen unter anderem Human Computer Interaction and Computer Vision as Service; Service-oriented Geovisualization Systems; Algorithm Engineering for Service-oriented Systems; Modeling and Verification of Self-adaptive Service-oriented Systems; Tools and Methods for Software Engineering in Service-oriented Systems; Security Engineering of Service-based IT Systems; Service-oriented Information Systems; Evolutionary Transition of Enterprise Applications to Service Orientation; Operating System Abstractions for Service-oriented Computing; sowie Services Specification, Composition, and Enactment. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 138 KW - Hasso Plattner Institute KW - research school KW - Ph.D. retreat KW - service-oriented systems engineering KW - Hasso-Plattner-Institut KW - Forschungskolleg KW - Klausurtagung KW - Service-oriented Systems Engineering Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-504132 SN - 978-3-86956-513-2 SN - 1613-5652 SN - 2191-1665 IS - 138 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Friedrich, Tobias A1 - Kötzing, Timo A1 - Krejca, Martin Stefan T1 - Unbiasedness of estimation-of-distribution algorithms JF - Theoretical computer science N2 - In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics - especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-lambda-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, lambda-MMAS(IB), and cGA. We show that an n-Bernoulli-lambda-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [0, 1](n). By restricting how an n-Bernoulli-lambda-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased. (C) 2018 Elsevier B.V. All rights reserved. KW - Estimation-of-distribution algorithm KW - Unbiasedness KW - Theory Y1 - 2019 U6 - https://doi.org/10.1016/j.tcs.2018.11.001 SN - 0304-3975 SN - 1879-2294 VL - 785 SP - 46 EP - 59 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Friedrich, Tobias A1 - Krejca, Martin Stefan A1 - Rothenberger, Ralf A1 - Arndt, Tobias A1 - Hafner, Danijar A1 - Kellermeier, Thomas A1 - Krogmann, Simon A1 - Razmjou, Armin T1 - Routing for on-street parking search using probabilistic data JF - AI communications : AICOM ; the European journal on artificial intelligence N2 - A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers. KW - Parking search KW - probabilistic routing KW - constrained optimization KW - field study Y1 - 2019 U6 - https://doi.org/10.3233/AIC-180574 SN - 0921-7126 SN - 1875-8452 VL - 32 IS - 2 SP - 113 EP - 124 PB - IOS Press CY - Amsterdam ER - TY - GEN A1 - Friedrich, Tobias T1 - From graph theory to network science BT - the natural emergence of hyperbolicity (Tutorial) T2 - 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) N2 - Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions. KW - Graph Theory KW - Graph Algorithms KW - Network Science KW - Hyperbolic Geometry Y1 - 2019 SN - 978-3-95977-100-9 U6 - https://doi.org/10.4230/LIPIcs.STACS.2019.5 VL - 126 PB - Schloss Dagstuhl-Leibniz-Zentrum für Informatik CY - Dragstuhl ER - TY - RPRT A1 - Döllner, Jürgen Roland Friedrich A1 - Friedrich, Tobias A1 - Arnrich, Bert A1 - Hirschfeld, Robert A1 - Lippert, Christoph A1 - Meinel, Christoph T1 - Abschlussbericht KI-Labor ITSE T1 - Final report "AI Lab ITSE" BT - KI-Labor für Methodik, Technik und Ausbildung in der IT-Systemtechnik N2 - Der Abschlussbericht beschreibt Aufgaben und Ergebnisse des KI-Labors "ITSE". Gegenstand des KI-Labors bildeten Methodik, Technik und Ausbildung in der IT-Systemtechnik zur Analyse, Planung und Konstruktion KI-basierter, komplexer IT-Systeme. N2 - Final Report on the "AI Lab ITSE" dedicated to Methodology, Technology and Education of AI in IT-Systems Engineering. KW - Abschlussbericht KW - KI-Labor KW - final report KW - AI Lab Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-578604 ER - TY - JOUR A1 - Casel, Katrin A1 - Fischbeck, Philipp A1 - Friedrich, Tobias A1 - Göbel, Andreas A1 - Lagodzinski, J. A. Gregor T1 - Zeros and approximations of Holant polynomials on the complex plane JF - Computational complexity : CC N2 - We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial. KW - Holant problems KW - approximate counting KW - partition functions KW - graph KW - polynomials Y1 - 2022 U6 - https://doi.org/10.1007/s00037-022-00226-5 SN - 1016-3328 SN - 1420-8954 VL - 31 IS - 2 PB - Springer CY - Basel ER - TY - JOUR A1 - Bläsius, Thomas A1 - Friedrich, Tobias A1 - Lischeid, Julius A1 - Meeks, Kitty A1 - Schirneck, Friedrich Martin T1 - Efficiently enumerating hitting sets of hypergraphs arising in data profiling JF - Journal of computer and system sciences : JCSS N2 - The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases. KW - Data profiling KW - Enumeration algorithm KW - Minimal hitting set KW - Transversal hypergraph KW - Unique column combination KW - W[3]-Completeness Y1 - 2022 U6 - https://doi.org/10.1016/j.jcss.2021.10.002 SN - 0022-0000 SN - 1090-2724 VL - 124 SP - 192 EP - 213 PB - Elsevier CY - San Diego ER - TY - GEN A1 - Blaesius, Thomas A1 - Eube, Jan A1 - Feldtkeller, Thomas A1 - Friedrich, Tobias A1 - Krejca, Martin Stefan A1 - Lagodzinski, Gregor J. A. A1 - Rothenberger, Ralf A1 - Severin, Julius A1 - Sommer, Fabian A1 - Trautmann, Justin T1 - Memory-restricted Routing With Tiled Map Data T2 - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC) N2 - Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*. Y1 - 2018 SN - 978-1-5386-6650-0 U6 - https://doi.org/10.1109/SMC.2018.00567 SN - 1062-922X SP - 3347 EP - 3354 PB - IEEE CY - New York ER - TY - GEN A1 - Bilo, Davide A1 - Friedrich, Tobias A1 - Lenzner, Pascal A1 - Melnichenko, Anna T1 - Geometric Network Creation Games T2 - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures N2 - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design. KW - Network creation games KW - edge-weighted networks KW - price of anarchy KW - Nash equilibrium KW - game dynamics KW - computational hardness Y1 - 2019 SN - 978-1-4503-6184-2 U6 - https://doi.org/10.1145/3323165.3323199 SP - 323 EP - 332 PB - Association for Computing Machinery CY - New York ER -