TY - GEN A1 - Hartmann, Carsten A1 - Banisch, Ralf A1 - Sarich, Marco A1 - Badowski, Thomas A1 - Schütte, Christof T1 - Characterization of Rare Events in Molecular Dynamics N2 - A good deal of molecular dynamics simulations aims at predicting and quantifying rare events, such as the folding of a protein or a phase transition. Simulating rare events is often prohibitive, especially if the equations of motion are high-dimensional, as is the case in molecular dynamics. Various algorithms have been proposed for efficiently computing mean first passage times, transition rates or reaction pathways. This article surveys and discusses recent developments in the field of rare event simulation and outlines a new approach that combines ideas from optimal control and statistical mechanics. The optimal control approach described in detail resembles the use of Jarzynski's equality for free energy calculations, but with an optimized protocol that speeds up the sampling, while (theoretically) giving variance-free estimators of the rare events statistics. We illustrate the new approach with two numerical examples and discuss its relation to existing methods. T3 - ZIB-Report - 13-51 KW - rare events KW - moleculare dynamics KW - optimal pathways KW - stochastic control KW - dynamic programming KW - change of measure KW - cumulant generating function Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42410 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Stephan, Rüdiger T1 - Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming N2 - In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004. T3 - ZIB-Report - 11-54 KW - hop constraints KW - chains KW - dynamic programming KW - facets Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14914 SN - 1438-0064 ER - TY - GEN A1 - Krumke, Sven A1 - Marathe, Madhav A1 - Poensgen, Diana A1 - Ravi, Sekharipuram S. A1 - Wirth, Hans-Christoph T1 - Budgeted Maximal Graph Coverage N2 - An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star. T3 - ZIB-Report - 02-24 KW - budgeted maximum coverage KW - approximation algorithm KW - dynamic programming Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6918 ER -