We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.
This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.
This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips. 相似文献
We present a Bayesian theory of object identification. Here, identifying an object means selecting a particular observation from a group of observations (variants), this observation (the regular variant) being characterized by a distributional model. In this sense, object identification means assigning a given model to one of several observations. Often, it is the statistical model of the regular variant, only, that is known. We study an estimator which relies essentially on this model and not on the characteristics of the “irregular” variants. In particular, we investigate under what conditions this variant selector is optimal. It turns out that there is a close relationship with exchangeability and Markovian reversibility. We finally apply our theory to the case of irregular variants generated from the regular variant by a Gaussian linear model. 相似文献
In this paper we discuss the existence of generic long-range correlations in spatially homogeneous and stable equilibrium states of closed lattice gas automata whose stochastic collision rules violate the symmetry conditions of detailed balance and in addition satisfy local conservation laws. Such correlations occur even though the collision rules are strictly local and invariant under all symmetries of the lattice. First a phenomenological (Langevin equation) approach is discussed. Next we present a theoretical analysis on the basis of an approximate microscopic (ring kinetic) theory. This theory is used to calculate the amplitude ofr– tails in the spatial correlations, and the result is compared with computer simulations. 相似文献
We have developed a process that significantly reduces the number of rotamers in computational protein design calculations. This process, which we call Vegas, results in dramatic computational performance increases when used with algorithms based on the dead-end elimination (DEE) theorem. Vegas estimates the energy of each rotamer at each position by fixing each rotamer in turn and utilizing various search algorithms to optimize the remaining positions. Algorithms used for this context specific optimization can include Monte Carlo, self-consistent mean field, and the evaluation of an expression that generates a lower bound energy for the fixed rotamer. Rotamers with energies above a user-defined cutoff value are eliminated. We found that using Vegas to preprocess rotamers significantly reduced the calculation time of subsequent DEE-based algorithms while retaining the global minimum energy conformation. For a full boundary design of a 51 amino acid fragment of engrailed homeodomain, the total calculation time was reduced by 12-fold. 相似文献
Computational methods play a central role in the rational design of novel proteins. The present work describes a new hybrid exact rotamer optimization (HERO) method that builds on previous dead-end elimination algorithms to yield dramatic performance enhancements. Measured on experimentally validated physical models, these improvements make it possible to perform previously intractable designs of entire protein core, surface, or boundary regions. Computational demonstrations include a full core design of the variable domains of the light and heavy chains of catalytic antibody 48G7 FAB with 74 residues and 10(128) conformations, a full core/boundary design of the beta1 domain of protein G with 25 residues and 10(53) conformations, and a full surface design of the beta1 domain of protein G with 27 residues and 10(60) conformations. In addition, a full sequence design of the beta1 domain of protein G is used to demonstrate the strong dependence of algorithm performance on the exact form of the potential function and the fidelity of the rotamer library. These results emphasize that search algorithm performance for protein design can only be meaningfully evaluated on physical models that have been subjected to experimental scrutiny. The new algorithm greatly facilitates ongoing efforts to engineer increasingly complex protein features. 相似文献
The influence of the Bardeen-Herring back-jump correlations on the Fermi-Dirac statistics of the one-dimensional nonhomogeneous fermionic lattice gas is studied by the Monte Carlo simulation technique and semianalytically. The resulting distribution is obtained, exhibiting increased population of the lower levels in comparison to the Fermi-Dirac statistics. 相似文献
In this article, we present an information gain-based variant of the next best view problem for occluded environment. Our proposed method utilizes a belief model of the unobserved space to estimate the expected information gain of each possible viewpoint. More precise, this belief model allows a more precise estimation of the visibility of occluded space and with that a more accurate prediction of the potential information gain of new viewing positions. We present experimental evaluation on a robotic platform for active data acquisition, however due to the generality of our approach it also applies to a wide variety of 3D reconstruction problems. With the evaluation done in simulation and on a real robotic platform, exploring and acquiring data from different environments we demonstrate the generality and usefulness of our approach for next best view estimation and autonomous data acquisition. 相似文献