Suchergebnisse

This volume documents the contributions of the conference 'Digital Editions between Experiment and Standardization', which took place on December 6?8, 2007 in the Heinz Nixdorf Museum Forum in Paderborn. It contains the written versions of the oral presentations ? here for the most part greatly expanded ? as well as summaries of the panel discussions of the three conference sections: concepts of digital editions,data formats for written music, and problems of encoding letters, diaries etc. Peter Stadler, Paderborn undJoachim Veit, Universität Paderborn.

The traditional way of tackling discrete optimization problems is by using local search on suitably defined cost or fitness landscapes. Such approaches are however limited by the slowing down that occurs when the local minima that are a feature of the typically rugged landscapes encountered arrest the progress of the search process. Another way of tackling optimization problems is by the use of heuristic approximations to estimate a global cost minimum. Here, we present a combination of these two approaches by using cover-encoding maps which map processes from a larger search space to subsets of the original search space. The key idea is to construct cover-encoding maps with the help of suitable heuristics that single out near-optimal solutions and result in landscapes on the larger search space that no longer exhibit trapping local minima. We present cover-encoding maps for the problems of the traveling salesman, number partitioning, maximum matching and maximum clique; the practical feasibility of our method is demonstrated by simulations of adaptive walks on the corresponding encoded landscapes which find the global minima for these problems. ; Open access funding provided by Max Planck Society. KK acknowledges funding from MINECO through the Ramón y Cajal program and through project SPASIMM, FIS2016-80067-P (AEI/FEDER, EU). This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant Agreement No. 694925). ; Peer reviewed

AbstractThe network Laplacian spectral density calculation is critical in many fields, including physics, chemistry, statistics, and mathematics. It is highly computationally intensive, limiting the analysis to small networks. Therefore, we present two efficient alternatives: one based on the network's edges and another on the degrees. The former gives the exact spectral density of locally tree-like networks but requires iterative edge-based message-passing equations. In contrast, the latter obtains an approximation of the spectral density using only the degree distribution. The computational complexities are 𝒪(|E|log(n)) and 𝒪(n), respectively, in contrast to 𝒪(n3) of the diagonalization method, where n is the number of vertices and |E| is the number of edges.