An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem

We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.     

Generalization bounds of ERM algorithm with Markov chain samples

One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed （i.i.d.） samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization （ERM） algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain samples is consistent. The established theory underlies application of ERM type of learning algorithms.     

Rotamer optimization for protein design through MAP estimation and problem‐size reduction

The search for the global minimum energy conformation (GMEC) of protein side chains is an important computational challenge in protein structure prediction and design. Using rotamer models, the problem is formulated as a NP‐hard optimization problem. Dead‐end elimination (DEE) methods combined with systematic A* search (DEE/A*) has proven useful, but may not be strong enough as we attempt to solve protein design problems where a large number of similar rotamers is eligible and the network of interactions between residues is dense. In this work, we present an exact solution method, named BroMAP (branch‐and‐bound rotamer optimization using MAP estimation), for such protein design problems. The design goal of BroMAP is to be able to expand smaller search trees than conventional branch‐and‐bound methods while performing only a moderate amount of computation in each node, thereby reducing the total running time. To achieve that, BroMAP attempts reduction of the problem size within each node through DEE and elimination by lower bounds from approximate maximum‐a‐posteriori (MAP) estimation. The lower bounds are also exploited in branching and subproblem selection for fast discovery of strong upper bounds. Our computational results show that BroMAP tends to be faster than DEE/A* for large protein design cases. BroMAP also solved cases that were not solved by DEE/A* within the maximum allowed time, and did not incur significant disadvantage for cases where DEE/A* performed well. Therefore, BroMAP is particularly applicable to large protein design problems where DEE/A* struggles and can also substitute for DEE/A* in general GMEC search. © 2009 Wiley Periodicals, Inc. J Comput Chem, 2009     

Silver Nanoparticle Formation in Different Sizes Induced by Peptides Identified within Split‐and‐Mix Libraries

Split‐and‐mix libraries are an excellent tool for the identification of peptides that induce the formation of Ag nanoparticles in the presence of either light or sodium ascorbate to reduce Ag⁺ ions. Structurally diverse peptides were detected in colorimetric on‐bead screenings that generate Ag nanoparticles of different sizes, as confirmed by SEM and X‐ray powder diffraction studies.

     

Linear bound on extremal functions of some forbidden patterns in 0-1 matrices

In this note by saying that a 0-1 matrix A avoids a pattern P given as a 0-1 matrix we mean that no submatrix of A either equals P or can be transformed into P by replacing some 1 entries with 0 entries. We present a new method for estimating the maximal number of the 1 entries in a matrix that avoids a certain pattern. Applying this method we give a linear bound on the maximal number of the 1 entries in an n by n matrix avoiding pattern L₁ and thereby we answer the question that was asked by Gábor Tardos. Furthermore, we use our approach on patterns related to L₁.     

A concentration result with application to subgraph count

Let H = (V,E) be a k ‐uniform hypergraph with a vertex set V and an edge set E. Let V _p be constructed by taking every vertex in V independently with probability p. Let X be the number of edges in E that are contained in V _p. We give a condition that guarantees the concentration of X within a small interval around its mean. The applicability of this result is demonstrated by deriving new sub‐Gaussian tail bounds for the number of copies of small complete and complete bipartite graphs in the binomial random graph. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

类锂离子(Z=21～30)1s~22s和1s~22p态近核处电子密度的下限(英文)

应用行列式条件和电子-原子核尖点(cusp)条件计算了核电荷数Z=21～30的类锂离子1s~22s和1s~2p态近核处电子密度的理论下限.该下限由Angulo和Dehesa等人推导(见Phys.Rev.A 42 641(1990))的包含两个或者更多径向期待值的不等式给出.结果表明,该下限对于高核电荷离子也同样适用,而且其品质要好于以前所知道的;计算中所用的波函数在这些具有较高核电荷离子体系的整个组态空间中都是准确可靠的.     

Equations of convolution type with monotone coefficients

This paper studies convolution type linear difference equations with coefficients satisfying some monotonicity properties. Methods from renewal theory are employed to obtain easily verified conditions for asymptotic stability of the zero solution, in terms of the coefficient sequence. Explicit bounds and rates of convergence are also considered, and an application to norms of matrix inverses is included.