Geometric quadrisection in linear time, with application to VLSI placement

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.     

THE MODELING AND ESTIMATION OF THE SHORT-RUN SUPPLY OF ROUNDWOOD UNDER NONLINEAR INCOME TAXES

This paper deals with the theory and estimation of the short-run supply of roundwood under nonlinear (progressive) income taxation. The theoretical part of the paper uses the two-period consumption harvesting model to introduce nonlinear income taxes into the forest management problem and presents a simple method to determine the optimal supply of roundwood in this case. In the empirical part of the paper, the model is specified in a way suitable for econometric analysis. The estimation method is the maximum likelihood method, and the estimation results seem to support the theoretical model. Finally, some results from model simulation imply that income taxation may have a nonnegligible impact on the supply of roundwood.     

A competitive (dual) simplex method for the assignment problem

Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling. - Sir John (from Michael Innes,The Open House (A Sir John Appleby Mystery), Penguin Books, 1974).A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asx _ij < 0. A choice (i,j) over columnsj having at least 3 basic activities that minimizesx _ij is shown to converge in at most ( ₂ ^n-1 ) pivots, and at most O(n ³) time, and it is argued that on average the number of pivots is at mostn logn. Dedicated with affection to George B. Dantzig on the occasion of his seventieth birthday.     

2D F/F NOESY for the assignment of NMR spectra of fluorochemicals

Two-dimensional (2D) NMR is an invaluable technique for the complete analysis and assignment of chemical structures. Although ¹⁹F/¹⁹F COSY experiments are routinely used for assignments in perfluorochemicals, interpretation can be difficult because four-bond (⁴J_FF) coupling constants are typically 5-10-fold larger than vicinal (³J_FF) coupling constants. Furthermore, the dependence of long range coupling constants on stereochemistry is not always known. Fluorine-fluorine NOESY correlations represent an enhancement in the arsenal of 2D ¹⁹F NMR experiments. The NOESY and COSY spectra of 2,2,3,3,4,4,4-heptafluorobutanol and a telomeric perfluorochemical iodide show that COSY identifies the 1,4-fluorine interactions whereas NOESY identifies the vicinal fluorine atoms. The combined experiments have been used to unambiguously assign all of the fluorines in a mixture of cis- and trans-perfluoro-1,3-dimethylcyclohexane and in a substituted perfluorotetrahydrofuran.     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

自然科学基金资助计划和支出预算的平衡

在政府推进部门预算制度和财政拨款管理制度改革的大环境下,国家自然科学基金逐渐采用预算管理制度,因此需要平衡资助计划和支出预算．本文在建立科学基金计划和预算的协调模型中,提出计划批准对年度支出敏感度的概念,设计了对经费使用的计划和支出纵横两维拨付的动态监控方法．并且通过模型的计算,可以快速给出综合考虑资助计划发展和使用经费有效两个方面因素的多种方案,供决策者参考．     

氨基甲酸酯类农药的密度泛函理论计算及拉曼光谱研究

为了获得氨基甲酸酯类农药分子的分子结构振动信息,应用密度泛函理论(DFT)中的B3LYP杂化泛函和6-31G(d,p)基组对三种氨基甲酸酯类农药(西维因、克百威和涕灭威)分子进行了几何结构优化和频率计算,利用拉曼光谱仪采集了这三种氨基甲酸酯类农药的实验拉曼光谱,并将理论方法计算的拉曼光谱和实验拉曼光谱进行比较。结果表明,理论方法计算的结果与实验值具有很好的匹配性。对三种氨基甲酸酯类农药分子在400～3 200 cm-1范围内的振动频率进行了全面地归属,找到了氨基甲酸酯类农药分子的四个特征峰,分别位于874,1 014,1 162和1 716 cm-1附近。对比分析三种农药实验拉曼光谱的差异,找到三种农药分子各自不同的特征峰。研究结果为氨基甲酸酯类农药的检测分析提供了理论基础,将应用于农产品中氨基甲酸酯类农药残留的鉴别。     

Energy Transfer from the Upper Triplet States of Aromatic Molecules

The energy transfer from the upper triplet states of diphenylamine, naphthalene and triphenylene to toluene and hexene-1 is studed. Two mechanisms of dissipation transferred energy in solvents are discussed.     

Simple matching vs linear assignment in scheduling models with positional effects: A critical review

This paper addresses scheduling models in which a contribution of an individual job to the objective function is represented by the product of its processing time and a certain positional weight. We review most of the known results in the area and demonstrate that a linear assignment algorithm as part of previously known solution procedures can be replaced by a faster matching algorithm that minimizes a linear form over permutations. Our approach reduces the running time of the resulting algorithms by up to two orders, and carries over to a wider range of models, with more general positional effects. Besides, the same approach works for the models with no prior history of study, e.g., parallel machine scheduling with deterioration and maintenance to minimize total flow time.     

Quantifier-free epistemic term-modal logic with assignment operator

In standard epistemic logic, the names and the existence of agents are usually assumed to be common knowledge implicitly. This is unreasonable for various applications in computer science and philosophy. Inspired by term-modal logic and assignment operators in dynamic logic, we introduce a lightweight modal predicate logic where names can be non-rigid, and the existence of agents can be uncertain. The language can handle various de dicto/de re distinctions in a natural way. We characterize the expressive power of our language, obtain complete axiomatisations of the logics over several classes of varying-domain/constant-domain epistemic models, and show their (un)decidability.