| [home] - [up] |
Abstract: We will introduce various tree-like decompositions of hypergraphs and characterize these by search games such as Seymour and Thomas's "Robber and Cops" game.
Colloquium - 16 Uhr s.t.
Abstract: We consider the problem of folding a given string of 0's and 1's on a lattice so that the string forms a self-avoiding walk and the number of pairs of adjacent 1's is maximized. This optimization problem is motivated by applications to simple models of protein folding. On the 2D and 3D square lattices, this problem is known to be NP-hard. Approximation algorithms for these two variants were first introduced by Hart and Istrail in 1995. They presented linear-time algorithms with approximation guarantees of 1/4 and 3/8 for the 2D and 3D problems, respectively.
For the 2D problem, we present a simple, linear-time, 1/3-approximation algorithm. We also show that the upper bound used in this algorithm and in that of Hart and Istrail can not be used to obtain an approximation factor better than 1/2. We then discuss a connection between the 3D problem and a combinatorial problem on binary strings, which may be of independent interest: Given a binary string of a's and b's, can we find a long subsequence of the string in which every sequence of consecutive a's is followed by at least as many consecutive b's? We show a non-trivial lower bound on the existence of such subsequences and use this to obtain a slightly improved algorithm for the 3D string folding problem.