@misc{HartmannBanischSarichetal.2013, author = {Hartmann, Carsten and Banisch, Ralf and Sarich, Marco and Badowski, Thomas and Sch{\"u}tte, Christof}, title = {Characterization of Rare Events in Molecular Dynamics}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42410}, year = {2013}, abstract = {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.}, language = {en} } @misc{GroetschelStephan2012, author = {Gr{\"o}tschel, Martin and Stephan, R{\"u}diger}, title = {Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14914}, year = {2012}, abstract = {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.}, language = {en} } @misc{KrumkeMarathePoensgenetal.2002, author = {Krumke, Sven and Marathe, Madhav and Poensgen, Diana and Ravi, Sekharipuram S. and Wirth, Hans-Christoph}, title = {Budgeted Maximal Graph Coverage}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6918}, number = {02-24}, year = {2002}, abstract = {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.}, language = {en} }