TY  - JOUR
A1  - Birnick, Johann
A1  - Bläsius, Thomas
A1  - Friedrich, Tobias
A1  - Naumann, Felix
A1  - Papenbrock, Thorsten
A1  - Schirneck, Friedrich Martin
T1  - Hitting set enumeration with partial information for unique column combination discovery
JF  - Proceedings of the VLDB Endowment
N2  - Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations. <br /> In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
Y1  - 2020
U6  - https://doi.org/10.14778/3407790.3407824
SN  - 2150-8097
VL  - 13
IS  - 11
SP  - 2270
EP  - 2283
PB  - Association for Computing Machinery
CY  - [New York, NY]
ER  - 
TY  - JOUR
A1  - Blaesius, Thomas
A1  - Friedrich, Tobias
A1  - Schirneck, Friedrich Martin
T1  - The complexity of dependency detection and discovery in relational databases
JF  - Theoretical computer science
N2  - Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
KW  - data profiling
KW  - enumeration complexity
KW  - functional dependency
KW  - inclusion
KW  - dependency
KW  - parameterized complexity
KW  - parsimonious reduction
KW  - transversal hypergraph
KW  - Unique column combination
KW  - W[3]-completeness
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.11.020
SN  - 0304-3975
SN  - 1879-2294
VL  - 900
SP  - 79
EP  - 96
PB  - Elsevier
CY  - Amsterdam
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  - 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  - 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  - Shi, Feng
A1  - Schirneck, Friedrich Martin
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Neumann, Frank
T1  - Correction to: Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
JF  - Algorithmica : an international journal in computer science
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  - 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  - JOUR
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
A1  - Sutton, Andrew M.
T1  - Robustness of Ant Colony Optimization to Noise
JF  - Evolutionary computation
N2  - Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo- Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical (mu + 1) EA outperforms any ACO algorithm, with smaller mu being better; however, in the case of large noise, the (mu + 1) EA fails, even for high values of mu (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor. is small enough, dependent on the variance s2 of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.
KW  - Ant colony optimization
KW  - Noisy Fitness
KW  - Theory
KW  - Run time analysis
Y1  - 2016
U6  - https://doi.org/10.1162/EVCO_a_00178
SN  - 1063-6560
SN  - 1530-9304
VL  - 24
SP  - 237
EP  - 254
PB  - MIT Press
CY  - Cambridge
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  - Riechelman, Dana F. C.
A1  - Fohlmeister, Jens Bernd
A1  - Kluge, Tobias
A1  - Jochum, Klaus Peter
A1  - Richter, Detlev K.
A1  - Deininger, Michael
A1  - Friedrich, Ronny
A1  - Frank, Norbert
A1  - Scholz, Denis
T1  - Evaluating the potential of tree-ring methodology for cross-dating of three annually laminated stalagmites from Zoolithencave (SE Germany)
JF  - Quaternary geochronology : the international research and review journal on advances in quaternary dating techniques
N2  - Three small stalagmites from Zoolithencave (southern Germany) show visible laminae, which consist of a clear and a brownish, pigmented layer pair. This potentially provides the opportunity to construct precise chronologies by counting annual laminae. The growth period of the three stalagmites was constrained by the C-14 bomb peak in the youngest part of all three stalagmites and C-14-dating of a piece of charcoal in the consolidated base part of stalagmite Zoo-rez-2. These data suggest an age of AD 1970 for the top laminae and a lower age limit of AD 1973-1682 or AD 1735-1778. Laminae were counted and their thickness determined on scanned thin sections of all stalagmites. On stalagmites Zoo-rez-1 and -2, three tracks were measured near the growth axes, each separated into three sections at prominent anchor laminae (I, II, III). Each section was replicated three times (a, b, c). For Zoo-rez-3, only one track was measured. The total number of laminae counted for Zoo-rez-1 ranges from 138 to 177, for Zoo-rez-2 from 119 to 145, and for Zoo-rez-3 from 159 to 166. The numbers agree well with the range constrained by the bomb peak and the age of the charcoal, which supports the annual origin of the laminae. The replicated measurements of the different tracks as well as the three different tracks on the stalagmites Zoo-rez-1 and-2 were cross-dated using the TSAP-Win (R) tree-ring software. This software is very useful for cross-dating because it enables to insert or delete missing or false laminae as well as identifying common pattern by shifting the series back and forth in time. However, visual inspection of the thin sections was necessary to confirm detection of missing or false laminae by TSAP-Win (R). For all three Zoo-rez speleothems, crossdating of the mean lamina thickness series was not possible due to a missing common pattern. The cross-dating procedure results in three refined chronologies for the three Zoo-rez stalagmites of ranging from AD 1821-1970 (Zoo-rez-1), AD 1835-1970 (Zoo-rez-2), and AD 1808-1970 (Zoo-rez-3).
KW  - Speleothems
KW  - Annual laminae
KW  - Lamina thickness
KW  - C-14 bomb peak
KW  - Tree-ring software
KW  - Cross-dating
Y1  - 2019
U6  - https://doi.org/10.1016/j.quageo.2019.04.001
SN  - 1871-1014
SN  - 1878-0350
VL  - 52
SP  - 37
EP  - 50
PB  - Elsevier
CY  - Oxford
ER  - 
TY  - JOUR
A1  - Friedrich, Tobias
A1  - Katzmann, Maximilian
A1  - Krohmer, Anton
T1  - Unbounded Discrepancy of Deterministic Random Walks on Grids
JF  - SIAM journal on discrete mathematics
N2  - Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [Combin. Probab. Comput., 15 (2006), pp. 815-822] showed that on Z(d), the single vertex discrepancy is only a constant c(d). Other authors also determined the precise value of c(d) for d = 1, 2. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph Z(d). We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions d >= 1 and arbitrary discrepancies l >= 0, we construct configurations that reach a discrepancy of at least l.
KW  - deterministic random walk
KW  - rotor-router model
KW  - single vertex discrepancy
Y1  - 2018
U6  - https://doi.org/10.1137/17M1131088
SN  - 0895-4801
SN  - 1095-7146
VL  - 32
IS  - 4
SP  - 2441
EP  - 2452
PB  - Society for Industrial and Applied Mathematics
CY  - Philadelphia
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  - 
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  - JOUR
A1  - Chauhan, Ankit
A1  - Friedrich, Tobias
A1  - Rothenberger, Ralf
T1  - Greed is good for deterministic scale-free networks
JF  - Algorithmica : an international journal in computer science
N2  - Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306-1325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both properties and exploit them to design faster algorithms for a number of classical graph problems. We complement their work by showing that some well-studied random graph models exhibit both of the mentioned PLB properties. PLB-U and PLB-N hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part we study three classical NP-hard optimization problems on PLB networks. It is known that on general graphs with maximum degree Delta, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Omega (ln Delta)-approximation forMinimum Vertex Cover and Minimum Dominating Set, and a Omega(Delta)-approximation forMaximum Independent Set. We prove that the PLB-U property with beta>2 suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that these problems are APX-hard even if PLB-U, PLB-N, and an additional power-law lower bound on the degree distribution hold. Hence, a PTAS cannot be expected unless P = NP. Furthermore, we prove that all three problems are in MAX SNP if the PLB-U property holds.
KW  - random graphs
KW  - deterministic properties
KW  - power-law
KW  - approximation
KW  - APX-hardness
Y1  - 2020
U6  - https://doi.org/10.1007/s00453-020-00729-z
SN  - 0178-4617
SN  - 1432-0541
VL  - 82
IS  - 11
SP  - 3338
EP  - 3389
PB  - Springer
CY  - New York
ER  - 
TY  - JOUR
A1  - Haase, Tobias
A1  - Krost, Annalena
A1  - Sauter, Tilman
A1  - Kratz, Karl
A1  - Peter, Jan
A1  - Kamann, Stefanie
A1  - Jung, Friedrich
A1  - Lendlein, Andreas
A1  - Zohlnhöfer, Dietlind
A1  - Rüder, Constantin
T1  - In vivo biocompatibility assessment of poly (ether imide) electrospun scaffolds
JF  - Journal of Tissue Engineering and Regenerative Medicine
N2  - Poly(ether imide) (PEI), which can be chemically functionalized with biologically active ligands, has emerged as a potential biomaterial for medical implants. Electrospun PEI scaffolds have shown advantageous properties, such as enhanced endothelial cell adherence, proliferation and low platelet adhesion in in vitro experiments. In this study, the in vivo behaviour of electrospun PEI scaffolds and PEI films was examined in a murine subcutaneous implantation model. Electrospun PEI scaffolds and films were surgically implanted subcutaneously in the dorsae of mice. The surrounding subcutaneous tissue response was examined via histopathological examination at 7 and 28days after implantation. No serious adverse events were observed for both types of PEI implants. The presence of macrophages or foreign body giant cells in the vicinity of the implants and the formation of a fibrous capsule indicated a normal foreign body reaction towards PEI films and scaffolds. Capsule thickness and inflammatory infiltration cells significantly decreased for PEI scaffolds during days 7-28 while remaining unchanged for PEI films. The infiltration of cells into the implant was observed for PEI scaffolds 7days after implantation and remained stable until 28days of implantation. Additionally some, but not all, PEI scaffold implants induced the formation of functional blood vessels in the vicinity of the implants. Conclusively, this study demonstrates the in vivo biocompatibility of PEI implants, with favourable properties of electrospun PEI scaffolds regarding tissue integration and wound healing.
KW  - poly(ether imide)
KW  - in vivo study
KW  - electrospun scaffold
KW  - capsule formation
KW  - foreign body giant cells
KW  - vascularization
Y1  - 2017
U6  - https://doi.org/10.1002/term.2002
SN  - 1932-6254
SN  - 1932-7005
VL  - 11
IS  - 4
SP  - 1034
EP  - 1044
PB  - Wiley
CY  - Hoboken
ER  - 
TY  - JOUR
A1  - Rüder, Constantin
A1  - Sauter, Tilman
A1  - Kratz, Karl
A1  - Haase, Tobias
A1  - Peter, Jan
A1  - Jung, Friedrich
A1  - Lendlein, Andreas
A1  - Zohlnhöfer, Dietlind
T1  - Influence of fibre diameter and orientation of electrospun copolyetheresterurethanes on smooth muscle and endothelial cell behaviour
JF  - Clinical hemorheology and microcirculation : blood flow and vessels
N2  - Polymers exhibiting cell-selective effects represent an extensive research field with high relevance for biomedical applications e.g. in the cardiovascular field supporting re-endothelialization while suppressing smooth muscle cell overgrowth. Such an endothelial cell-selective effect could be recently demonstrated for a copolyetheresterurethane (PDC) containing biodegradable poly(p-dioxanone) and poly(epsilon-caprolactone) segments, which selectively enhanced the adhesion of human umbilical vein endothelial cells (HUVEC) while suppressing the attachment of smooth muscle cells (SMC).
 In this study we investigated the influence of the fibre orientation (random and aligned) and fibre diameter (2 mu m and 500 nm) of electrospun PDC scaffolds on the adhesion, proliferation and apoptosis of HUVEC and SMC.
 Adhesion, viability and proliferation of HUVEC was diminished when the fibre diameter was reduced to a submicron scale, while the orientation of the microfibres did only slightly influence the cellular behaviour. In contrast, a submicron fibre diameter improved SMC viability. In conclusion, PDC scaffolds with micron-sized single fibres could be promising candidate materials for cell-selective stent coatings.
KW  - Endothelialization
KW  - drug eluting stent
KW  - degradable polymer
KW  - electrospinning
KW  - cell selectivity
Y1  - 2013
U6  - https://doi.org/10.3233/CH-131787
SN  - 1386-0291
SN  - 1875-8622
VL  - 55
IS  - 4
SP  - 513
EP  - 522
PB  - IOS Press
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Quinzan, Francesco
A1  - Göbel, Andreas
A1  - Wagner, Markus
A1  - Friedrich, Tobias
T1  - Evolutionary algorithms and submodular functions
BT  - benefits of heavy-tailed mutations
JF  - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal
N2  - A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area of work, we propose a new mutation operator and analyze its performance on the (1 + 1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1 + 1) EA on classes of problems for which results on the other mutation operators are available. We show that the (1 + 1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the (1 + 1) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the (1 + 1) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances.
KW  - Evolutionary algorithms
KW  - Mutation operators
KW  - Submodular functions
KW  - Matroids
Y1  - 2021
U6  - https://doi.org/10.1007/s11047-021-09841-7
SN  - 1572-9796
VL  - 20
IS  - 3
SP  - 561
EP  - 575
PB  - Springer Science + Business Media B.V.
CY  - Dordrecht
ER  - 
TY  - JOUR
A1  - Bauman, Spenser
A1  - Bolz, Carl Friedrich
A1  - Hirschfeld, Robert
A1  - Kirilichev, Vasily
A1  - Pape, Tobias
A1  - Siek, Jeremy G.
A1  - Tobin-Hochstadt, Sam
T1  - Pycket: A Tracing JIT for a Functional Language
JF  - ACM SIGPLAN notices
N2  - We present Pycket, a high-performance tracing JIT compiler for Racket. Pycket supports a wide variety of the sophisticated features in Racket such as contracts, continuations, classes, structures, dynamic binding, and more. On average, over a standard suite of benchmarks, Pycket outperforms existing compilers, both Racket's JIT and other highly-optimizing Scheme compilers. Further, Pycket provides much better performance for Racket proxies than existing systems, dramatically reducing the overhead of contracts and gradual typing. We validate this claim with performance evaluation on multiple existing benchmark suites.
 The Pycket implementation is of independent interest as an application of the RPython meta-tracing framework (originally created for PyPy), which automatically generates tracing JIT compilers from interpreters. Prior work on meta-tracing focuses on bytecode interpreters, whereas Pycket is a high-level interpreter based on the CEK abstract machine and operates directly on abstract syntax trees. Pycket supports proper tail calls and first-class continuations. In the setting of a functional language, where recursion and higher-order functions are more prevalent than explicit loops, the most significant performance challenge for a tracing JIT is identifying which control flows constitute a loop-we discuss two strategies for identifying loops and measure their impact.
KW  - Experimentation
KW  - Languages
KW  - Measurement
KW  - Performance
KW  - JIT compilers
KW  - contracts
KW  - tracing
KW  - functional languages
KW  - Racket
Y1  - 2015
U6  - https://doi.org/10.1145/2784731.2784740
SN  - 0362-1340
SN  - 1558-1160
VL  - 50
IS  - 9
SP  - 22
EP  - 34
PB  - Association for Computing Machinery
CY  - New York
ER  - 
TY  - JOUR
A1  - Pape, Tobias
A1  - Bolz, Carl Friedrich
A1  - Hirschfeld, Robert
T1  - Adaptive just-in-time value class optimization for lowering memory consumption and improving execution time performance
JF  - Science of computer programming
N2  - The performance of value classes is highly dependent on how they are represented in the virtual machine. Value class instances are immutable, have no identity, and can only refer to other value objects or primitive values and since they should be very lightweight and fast, it is important to optimize them carefully. In this paper we present a technique to detect and compress common patterns of value class usage to improve memory usage and performance. The technique identifies patterns of frequent value object references and introduces abbreviated forms for them. This allows to store multiple inter-referenced value objects in an inlined memory representation, reducing the overhead stemming from meta data and object references. Applied to a small prototype and an implementation of the Racket language, we found improvements in memory usage and execution time for several micro-benchmarks. (C) 2016 Elsevier B.V. All rights reserved.
KW  - Meta-tracing
KW  - JIT
KW  - Data structure optimization
KW  - Value classes
Y1  - 2017
U6  - https://doi.org/10.1016/j.scico.2016.08.003
SN  - 0167-6423
SN  - 1872-7964
VL  - 140
SP  - 17
EP  - 29
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Bläsius, Thomas
A1  - Freiberger, Cedric
A1  - Friedrich, Tobias
A1  - Katzmann, Maximilian
A1  - Montenegro-Retana, Felix
A1  - Thieffry, Marianne
T1  - Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
JF  - ACM Transactions on Algorithms
N2  - A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. <br /> To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
KW  - Random graphs
KW  - hyperbolic geometry
KW  - scale-free networks
KW  - bidirectional shortest path
Y1  - 2022
U6  - https://doi.org/10.1145/3516483
SN  - 1549-6325
SN  - 1549-6333
VL  - 18
IS  - 2
SP  - 1
EP  - 32
PB  - Association for Computing Machinery
CY  - New York
ER  - 
TY  - JOUR
A1  - Neffe, Axel T.
A1  - von Rüsten-Lange, Maik
A1  - Braune, Steffen
A1  - Lützow, Karola
A1  - Roch, Toralf
A1  - Richau, Klaus
A1  - Krüger, Anne
A1  - Becherer, Tobias
A1  - Thünemann, Andreas F.
A1  - Jung, Friedrich
A1  - Haag, Rainer
A1  - Lendlein, Andreas
T1  - Multivalent grafting of hyperbranched oligo- and polyglycerols shielding rough membranes to mediate hemocompatibility
JF  - Journal of materials chemistry : B, Materials for biology and medicine
N2  - Hemocompatible materials are needed for internal and extracorporeal biomedical applications, which should be realizable by reducing protein and thrombocyte adhesion to such materials. Polyethers have been demonstrated to be highly efficient in this respect on smooth surfaces. Here, we investigate the grafting of oligo- and polyglycerols to rough poly(ether imide) membranes as a polymer relevant to biomedical applications and show the reduction of protein and thrombocyte adhesion as well as thrombocyte activation. It could be demonstrated that, by performing surface grafting with oligo-and polyglycerols of relatively high polydispersity (>1.5) and several reactive groups for surface anchoring, full surface shielding can be reached, which leads to reduced protein adsorption of albumin and fibrinogen. In addition, adherent thrombocytes were not activated. This could be clearly shown by immunostaining adherent proteins and analyzing the thrombocyte covered area. The presented work provides an important strategy for the development of application relevant hemocompatible 3D structured materials.
Y1  - 2014
U6  - https://doi.org/10.1039/c4tb00184b
SN  - 2050-750X
SN  - 2050-7518
VL  - 2
IS  - 23
SP  - 3626
EP  - 3635
PB  - Royal Society of Chemistry
CY  - Cambridge
ER  - 
TY  - GEN
A1  - Neffe, Axel T.
A1  - von Rüsten-Lange, Maik
A1  - Braune, Steffen
A1  - Lützow, Karola
A1  - Roch, Toralf
A1  - Richau, Klaus
A1  - Krüger, Anne
A1  - Becherer, Tobias
A1  - Thünemann, Andreas F.
A1  - Jung, Friedrich
A1  - Haag, Rainer
A1  - Lendlein, Andreas
T1  - Multivalent grafting of hyperbranched oligo- and polyglycerols shielding rough membranes to mediate hemocompatibility
N2  - Hemocompatible materials are needed for internal and extracorporeal biomedical applications, which should be realizable by reducing protein and thrombocyte adhesion to such materials. Polyethers have been demonstrated to be highly efficient in this respect on smooth surfaces. Here, we investigate the grafting of oligo- and polyglycerols to rough poly(ether imide) membranes as a polymer relevant to biomedical applications and show the reduction of protein and thrombocyte adhesion as well as thrombocyte activation. It could be demonstrated that, by performing surface grafting with oligo- and polyglycerols of relatively high polydispersity (>1.5) and several reactive groups for surface anchoring, full surface shielding can be reached, which leads to reduced protein adsorption of albumin and fibrinogen. In addition, adherent thrombocytes were not activated. This could be clearly shown by immunostaining adherent proteins and analyzing the thrombocyte covered area. The presented work provides an important strategy for the development of application relevant hemocompatible 3D structured materials.
T3  - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 285 
Y1  - 2014
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-99444
ER  - 
TY  - BOOK
A1  - Wassermann, Lars
A1  - Felgentreff, Tim
A1  - Pape, Tobias
A1  - Bolz, Carl Friedrich
A1  - Hirschfeld, Robert
T1  - Tracing Algorithmic Primitives in RSqueak/VM
N2  - When realizing a programming language as VM, implementing behavior as part of the VM, as primitive, usually results in reduced execution times. But supporting and developing primitive functions requires more effort than maintaining and using code in the hosted language since debugging is harder, and the turn-around times for VM parts are higher. Furthermore, source artifacts of primitive functions are seldom reused in new implementations of the same language. And if they are reused, the existing API usually is emulated, reducing the performance gains. Because of recent results in tracing dynamic compilation, the trade-off between performance and ease of implementation, reuse, and changeability might now be decided adversely.

In this work, we investigate the trade-offs when creating primitives, and in particular how large a difference remains between primitive and hosted function run times in VMs with tracing just-in-time compiler. To that end, we implemented the algorithmic primitive BitBlt three times for RSqueak/VM. RSqueak/VM is a Smalltalk VM utilizing the PyPy RPython toolchain. We compare primitive implementations in C, RPython, and Smalltalk, showing that due to the tracing just-in-time compiler, the performance gap has lessened by one magnitude to one magnitude.
N2  - Wenn man eine Programmiersprache als Virtuelle Maschine (VM) realisiert, dann wird Verhalten, das man als Teil der VM, also primitiv, implementiert normalerweise schneller ausgeführt, als vergleichbare Funktionen die in der implementierten Sprache verfasst wurden. Aber die Entwicklung und Wartung von primitiven Funktionen erfordert mehr Anstrengung als die Wartung und Benutzung von Funktionen der implementierten Sprache, da Fehlerbehebung schwerer ist, und die Entwicklungszyklen für VM-Teile länger sind. Im Gegensatz zu Programmen, die in der implementierten Programmiersprache geschrieben sind, wird Quelltext von Primitiven selten wiederverwendet. Und falls sie wiederverwendet werden, dann wird die Schnittstelle zur VM meist emuliert, was den Geschwindigkeitsvorteil reduziert. Aber aufgrund von neueren Resultaten der ablaufverfolgenden dynamischen Kompilierung, könnte die Abwägung zwischen Geschwindigkeit einerseits und Implementierungsaufwand, Wiederverwendbarkeit und Änderbarkeit andererseits nun zugunsten von letzteren ausfallen.

In dieser Arbeit untersuchen wir, welche Abstriche bei der Implementierung von Verhalten als Primitive gemacht werden müssen, insbesondere wie hoch die Laufzeitunterschiede zwischen Primitiven und gehosteten Funktionen noch sind. Um das zu erreichen haben wir die algorithmische Primitive BitBlt drei mal für RSqueak/VM implementiert. RSqueak/VM ist eine Smalltalk VM, die die PyPy RPython-Toolkette verwendet. Wir vergleichen die Primitivenimplementierungen in C, RPython und Smalltalk, und zeigen, dass aufgrund eines ablaufverfolgenden just-in-time-Übersetzers der Geschwindigkeitsunterschied um eine Größenordnung auf eine Größenordnung gefallen ist.
T3  - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 104 
KW  - virtual machines
KW  - collection types
KW  - memory optimization
KW  - dynamic  typing
KW  - virtuelle Maschinen
KW  - Sammlungsdatentypen
KW  - Speicheroptimierungen
KW  - dynamische Sprachen
Y1  - 2016
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-91277
SN  - 978-3-86956-355-8
SN  - 1613-5652
SN  - 2191-1665
IS  - 104
PB  - Universitätsverlag Potsdam
CY  - Potsdam
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  - JOUR
A1  - Pape, Tobias
A1  - Felgentreff, Tim
A1  - Hirschfeld, Robert
A1  - Gulenko, Anton
A1  - Bolz, Carl Friedrich
T1  - Language-independent Storage Strategies for Tracing-JIT-based Virtual Machines
JF  - ACM SIGPLAN notices
N2  - Storage strategies have been proposed as a run-time optimization for the PyPy Python implementation and have shown promising results for optimizing execution speed and memory requirements. However, it remained unclear whether the approach works equally well in other dynamic languages. Furthermore, while PyPy is based on RPython, a language to write VMs with reusable components such as a tracing just-in-time compiler and garbage collection, the strategies design itself was not generalized to be reusable across languages implemented using that same toolchain. In this paper, we present a general design and implementation for storage strategies and show how they can be reused across different RPython-based languages. We evaluate the performance of our implementation for RSqueak, an RPython-based VM for Squeak/Smalltalk and show that storage strategies may indeed off er performance benefits for certain workloads in other dynamic programming languages. We furthermore evaluate the generality of our implementation by applying it to Topaz, a Ruby VM, and Pycket, a Racket implementation.
KW  - Implementation
KW  - collection types
KW  - memory optimization
KW  - dynamic typing
Y1  - 2016
U6  - https://doi.org/10.1145/2816707.2816716
SN  - 0362-1340
SN  - 1558-1160
VL  - 51
SP  - 104
EP  - 113
PB  - Association for Computing Machinery
CY  - New York
ER  - 
TY  - JOUR
A1  - Roostapour, Vahid
A1  - Neumann, Aneta
A1  - Neumann, Frank
A1  - Friedrich, Tobias
T1  - Pareto optimization for subset selection with dynamic cost constraints
JF  - Artificial intelligence
N2  - We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.
KW  - Subset selection
KW  - Submodular function
KW  - Multi-objective optimization
KW  - Runtime analysis
Y1  - 2022
U6  - https://doi.org/10.1016/j.artint.2021.103597
SN  - 0004-3702
SN  - 1872-7921
VL  - 302
PB  - Elsevier
CY  - Amsterdam
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  - JOUR
A1  - Cohen, Sarel
A1  - Hershcovitch, Moshik
A1  - Taraz, Martin
A1  - Kissig, Otto
A1  - Issac, Davis
A1  - Wood, Andrew
A1  - Waddington, Daniel
A1  - Chin, Peter
A1  - Friedrich, Tobias
T1  - Improved and optimized drug repurposing for the SARS-CoV-2 pandemic
JF  - PLoS one
N2  - The active global SARS-CoV-2 pandemic caused more than 426 million cases and 5.8 million deaths worldwide. The development of completely new drugs for such a novel disease is a challenging, time intensive process. Despite researchers around the world working on this task, no effective treatments have been developed yet. This emphasizes the importance of drug repurposing, where treatments are found among existing drugs that are meant for different diseases. A common approach to this is based on knowledge graphs, that condense relationships between entities like drugs, diseases and genes. Graph neural networks (GNNs) can then be used for the task at hand by predicting links in such knowledge graphs. Expanding on state-of-the-art GNN research, Doshi et al. recently developed the Dr-COVID model. We further extend their work using additional output interpretation strategies. The best aggregation strategy derives a top-100 ranking of 8,070 candidate drugs, 32 of which are currently being tested in COVID-19-related clinical trials. Moreover, we present an alternative application for the model, the generation of additional candidates based on a given pre-selection of drug candidates using collaborative filtering. In addition, we improved the implementation of the Dr-COVID model by significantly shortening the inference and pre-processing time by exploiting data-parallelism. As drug repurposing is a task that requires high computation and memory resources, we further accelerate the post-processing phase using a new emerging hardware-we propose a new approach to leverage the use of high-capacity Non-Volatile Memory for aggregate drug ranking.
Y1  - 2023
U6  - https://doi.org/10.1371/journal.pone.0266572
SN  - 1932-6203
VL  - 18
IS  - 3
PB  - PLoS
CY  - San Fransisco
ER  - 
TY  - BOOK
A1  - Kuban, Robert
A1  - Rotta, Randolf
A1  - Nolte, Jörg
A1  - Chromik, Jonas
A1  - Beilharz, Jossekin Jakob
A1  - Pirl, Lukas
A1  - Friedrich, Tobias
A1  - Lenzner, Pascal
A1  - Weyand, Christopher
A1  - Juiz, Carlos
A1  - Bermejo, Belen
A1  - Sauer, Joao
A1  - Coelh, Leandro dos Santos
A1  - Najafi, Pejman
A1  - Pünter, Wenzel
A1  - Cheng, Feng
A1  - Meinel, Christoph
A1  - Sidorova, Julia
A1  - Lundberg, Lars
A1  - Vogel, Thomas
A1  - Tran, Chinh
A1  - Moser, Irene
A1  - Grunske, Lars
A1  - Elsaid, Mohamed Esameldin Mohamed
A1  - Abbas, Hazem M.
A1  - Rula, Anisa
A1  - Sejdiu, Gezim
A1  - Maurino, Andrea
A1  - Schmidt, Christopher
A1  - Hügle, Johannes
A1  - Uflacker, Matthias
A1  - Nozza, Debora
A1  - Messina, Enza
A1  - Hoorn, André van
A1  - Frank, Markus
A1  - Schulz, Henning
A1  - Alhosseini Almodarresi Yasin, Seyed Ali
A1  - Nowicki, Marek
A1  - Muite, Benson K.
A1  - Boysan, Mehmet Can
A1  - Bianchi, Federico
A1  - Cremaschi, Marco
A1  - Moussa, Rim
A1  - Abdel-Karim, Benjamin M.
A1  - Pfeuffer, Nicolas
A1  - Hinz, Oliver
A1  - Plauth, Max
A1  - Polze, Andreas
A1  - Huo, Da
A1  - Melo, Gerard de
A1  - Mendes Soares, Fábio
A1  - Oliveira, Roberto Célio Limão de
A1  - Benson, Lawrence
A1  - Paul, Fabian
A1  - Werling, Christian
A1  - Windheuser, Fabian
A1  - Stojanovic, Dragan
A1  - Djordjevic, Igor
A1  - Stojanovic, Natalija
A1  - Stojnev Ilic, Aleksandra
A1  - Weidmann, Vera
A1  - Lowitzki, Leon
A1  - Wagner, Markus
A1  - Ifa, Abdessatar Ben
A1  - Arlos, Patrik
A1  - Megia, Ana
A1  - Vendrell, Joan
A1  - Pfitzner, Bjarne
A1  - Redondo, Alberto
A1  - Ríos Insua, David
A1  - Albert, Justin Amadeus
A1  - Zhou, Lin
A1  - Arnrich, Bert
A1  - Szabó, Ildikó
A1  - Fodor, Szabina
A1  - Ternai, Katalin
A1  - Bhowmik, Rajarshi
A1  - Campero Durand, Gabriel
A1  - Shevchenko, Pavlo
A1  - Malysheva, Milena
A1  - Prymak, Ivan
A1  - Saake, Gunter
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 2019
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 2019. Selected projects have presented their results on April 9th and November 12th 2019 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 2019 vorgestellt.  Ausgewählte Projekte stellten ihre Ergebnisse am 09. April und 12. November 2019 im Rahmen des Future SOC Lab Tags vor.
T3  - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 158 
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  - 2023
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-597915
SN  - 978-3-86956-564-4
SN  - 1613-5652
SN  - 2191-1665
IS  - 158
PB  - Universitätsverlag Potsdam
CY  - Potsdam
ER  - 
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  - Bläsius, Thomas
A1  - Friedrich, Tobias
A1  - Krejca, Martin S.
A1  - Molitor, Louise
T1  - The impact of geometry on monochrome regions in the flip Schelling process
JF  - Computational geometry
N2  - Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c>0 such that the expected fraction of monochrome edges after the FSP is at least 1/2+c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2+o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
KW  - Agent-based model
KW  - Schelling segregation
KW  - Spin system
Y1  - 2022
U6  - https://doi.org/10.1016/j.comgeo.2022.101902
SN  - 0925-7721
SN  - 1879-081X
VL  - 108
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - GEN
A1  - Blaesius, Thomas
A1  - Eube, Jan
A1  - Feldtkeller, Thomas
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Lagodzinski, Julius Albert Gregor
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  - JOUR
A1  - Casel, Katrin
A1  - Fischbeck, Philipp
A1  - Friedrich, Tobias
A1  - Göbel, Andreas
A1  - Lagodzinski, Julius Albert 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  -