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 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. 相似文献
This prospective clinical study aimed to evaluate the peri-implant hard tissue dimensional change at 6 months of immediate implant placement with bone graft materials in the posterior area using cone-beam computed tomography (CBCT). Twelve dental implants were placed concurrently following tooth extraction in the posterior area and filled with xenograft particles. The CBCT images were taken immediately after surgical procedures and then at 6 months follow-up. To evaluate the hard tissue changes, the vertical and horizontal bone thickness were analyzed and measured using ImageJ software. Paired t-test or Wilcoxon match-pair signed-rank test was done to analyze the changes of hard tissue values at the same level between immediately and 6 months following immediate implant placement. Independent t-test or Mann–Whitney U test was used to analyze the dimensional change in the vertical and horizontal direction in buccal and lingual aspects. The level of significance was set at p value = 0.05. All implants were successfully osseointegrated. At 6 months follow-up, the vertical bone change at the buccal aspect was −0.69 mm and at the lingual aspect −0.39 mm. For horizontal bone thickness, the bone dimensional changes at 0, 1, 5, and 9 mm levels from the implant platform were −0.62 mm, −0.70 mm, −0.24 mm, and −0.22 mm, respectively. A significant bone reduction was observed in all measurement levels during the 6 months after implant placement (p value < 0.05). It was noted that even with bone grafting, a decrease in bone thickness was seen following the immediate implant placement. Therefore, this technique can be an alternative method to place the implant in the posterior area. 相似文献
This paper investigates the exact and approximate spectrum assignment properties associated with realizable output-feedback pole-placement type controllers for single-input single-output linear time-invariant time-delay systems with commensurate point delays. The controller synthesis problem is discussed through the solvability of a set of coupled diophantine equations of polynomials. An extra complexity is incorporated to the above design to cancel extra unsuitable dynamics being generated when solving the above diophantine equations. Thus, the complete controller tracks any arbitrary prefixed (either finite or delaydependent) closed-loop spectrum. However, if the controller is simplified by deleting the above mentioned extra complexity, then the robust stability and approximated spectrum assignment are still achievable for a certain sufficiently small amount of delayed dynamics. Finally, the approximate spectrum assignment and robust stability problems are revisited under plant disturbances if the nominal controller is maintained. In the current approach, the finite spectrum assignment is only considered as a particular case to the designer‘s choice of a (delay-dependent) arbitrary spectrum assignment objective. 相似文献
In this paper a multi-input, multi-output (MIMO) active noise control system with the aim of global reduction of broadband noise in a telephone kiosk is addressed. The model selected for this optimization problem is the acoustic environment of an enclosure taking into account the effect of coupling of secondary sources used for control purpose. This optimization involves finding the best locations for loudspeakers and microphones inside the enclosure as well as optimizing the control signals considering secondary source coupling.Previous results show that in order to be able to reduce acoustic noise globally inside the enclosure, the frequency range of 50-300 Hz must be selected for control purpose. The mean of acoustic potential energy of the enclosure, when excited in this frequency range, is adopted as a performance measure. This performance index is penalized with the power of the signal required to excite secondary loudspeakers, in order to avoid placements that may need high voltage power amplifier for a desired performance. To find the solution of this problem, i.e. the global minimum of the performance index, several genetic algorithms are proposed and compared. In order to attain the best achievable performance in reaching the global minimum, the parameters of these genetic algorithms are tuned, and used for optimization purpose. Numerical simulations of the acoustical potential energy as well as the sound pressure at different heights of the kiosk, when active noise control (ANC) system operates, confirm the optimality of the locations proposed by the genetic algorithm. 相似文献
In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation. 相似文献
Within two-dimensional cutting and packing problems with irregular shaped objects, the concept of
-functions has been proven to be very helpful for several solution approaches. In order to construct such
-functions a previous work, in which so-called primary objects are considered, is continued. Now
-functions are constructed for pairs of objects which can be represented as a finite combination (union, intersection, complement) of primary objects which allows the handling of arbitrary shaped objects by appropriate approximations of sufficient accuracy.Received: October 2002, Revised: October 2003, AMS classification:
65K05, 90C26, 90B06All correspondence to: Guntram Scheithauer 相似文献