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. 相似文献
A strategy for constructing a global multivariate calibration model that includes calibration samples measured over time on different days is developed and applied in electroanalysis. Both synthetic and real samples (tap, extracted and river water) are analyzed by differential‐pulse anodic stripping voltammetry, showing the suitability of the global model constructed that provides successful results similar to those of the usual multivariate calibration. In addition the capability of discrimination of this model is evaluated in prediction for the mean of three replicates with estimation of probability of false noncompliance, α, and false compliance, β, being found 3.1, 11.2, 6.7 and 64.7 nM for nominal concentrations of zinc, cadmium, lead and copper of 96.0, 40.4, 37.3 and 328.0 nM respectively when α=β=0.05. It has been proven that the use of the global calibration does not imply a loss of multivariate analytical sensitivity, using this parameter as quality index of the analytical procedure. The viability of using calibration maintenance strategies with electroanalytical techniques is shown, providing a way to save time and experimental effort when these techniques are used in routine analysis. 相似文献
We present a characterisation of posets of size n with linear discrepancy n − 2. These are the posets that are “furthest” from a linear order without being an antichain.
This revised version was published online in September 2006 with corrections to the Cover Date. 相似文献
We present a characterization of confluence for term rewriting systems, which is then refined for special classes of rewriting systems. The refined characterization is used to obtain a polynomial time algorithm for deciding the confluence of ground term rewrite systems. The same approach also shows the decidability of confluence for shallow and linear term rewriting systems. The decision procedure has a polynomial time complexity under the assumption that the maximum arity of a function symbol in the signature is a constant. 相似文献