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.     

拟线性椭圆变分不等式的障碍最优控制问题

对拟线性椭圆变分不等式的障碍最优控制问题(即以障碍为控制变量)进行了研究．指标泛函为Lagrange型,其中含有控制变量二阶导数的p次幂,这使得最优性条件的推导颇为不易．对所考虑的问题给出了最优控制的存在性定理以及必要条件．     

Conceptions of function translation: obstacles, intuitions, and rerouting

A horizontal translation of a function is the focus of this study. We examine the explanations provided by secondary school students and secondary school teachers to a translation of a function, focusing on the example of the parabola y=(x−3)² and its relationship to y=x². The participants’ explanations focused on attending to patterns, locating the zero of the function, and the point-wise calculation of function values. The results confirm that the horizontal shift of the parabola is, at least initially, inconsistent with expectations and counterintuitive to most participants. We articulate possible sources of this perceived inconsistency and describe a pedagogical approach aimed at resolving it.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

关于解椭圆型问题的多子域D-N交替算法

构造一个求解椭圆型边值问题的多子域D—N交替算法，导出对应的容度方程和等价的迭代法，证明算法的收敛性。     

A Degenerate Stefan Problem with Two Free Boundaries

ＡＤｅｇｅｎｅｒａｔｅＳｔｅｆａｎＰｒｏｂｌｅｍｗｉｔｈＴｗｏＦｒｅｅＢｏｕｎｄａｒｉｅｓ￥（李辉来）ＬｉＨｕｉｌａｉ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ，１３００２３）Ａｂｓｔｒａｃｔ...     

作业车间调度问题的改进混合遗传算法

作业车间调度是一类求解困难的组合优化问题,本文在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法相结合,提出了一种基于遗传和禁忌搜索的混合算法,并用实例对该算法进行了仿真研究.结果表明,该算法有很好的收敛精度,是可行的,与传统的算法相比较,有明显的优越性.     

Diophantine Undecidability of Function Fields of Characteristic Greater than 2, Finitely Generated over Fields Algebraic over a Finite Field

Let F be a function field of characteristic p > 2, finitely generated over a field C algebraic over a finite field C _p and such that it has an extension of degree p. Then Hilbert's Tenth Problem is not decidable over F.     

Optimal control of the obstacle in a quasilinear elliptic variational inequality

In this paper we consider an obstacle control problem where the state satisfies a quasilinear elliptic variational inequality and the control function is the obstacle. The state is chosen to be close to the desire profile while the H² norms of the obstacle is not too large. Existence and necessary conditions for the optimal control are established.     

Optimale Quantisierung

Zusammenfassung. Optimale Quantisierungen oder – damit ?quivalent – minimale Summen von Momenten spielen in mehreren Zweigen der Mathematik und ihrer Anwendungen eine Rolle. Ausgehend von der Fejes Tóth'schen Ungleichung für Summen von Momenten in der euklidischen Ebene und einem zugeh?rigen Stabilit?tssatz, werden gewisse Erweiterungen auf normierte R?ume und riemannsche Mannigfaltigkeiten h?herer Dimension besprochen. Die Ergebnisse werden dann auf Probleme aus folgenden Bereichen angewendet: (i) Datenübertragung, (ii) Wahrscheinlichkeitstheorie, (iii) numerische Integration, (iv) Approximation konvexer K?rper und (v) isoperimetrische Probleme. Eingegangen am 29. Mai 2002 / Angenommen am 8. Juli 2002