Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].     

Seismic gyrotropy as a result of rock-microstructure dissymmetry

Seismic investigations show that rocks exhibit not only anisotropic properties but also gyrotropic ones. Recently, the phenomenological theory has been developed to describe the phenomenon ‘seismic gyrotropy'. The paper gives a possible explanation of the gyrotropic properties of rocks on a microlevel. A gyrotropic model of grainy rock with dissymetry in its microstructure is presented. The model is built on a principle ‘azimuthal turn plus translation'. The mathematical and physical formulations of the problem are discussed. An algorithm is constructed to find the displacements, their first and second derivatives with respect to spatial coordinates as well as stresses inside a grain, an element of the model. Mathematical modelling of elastic-wave propagation in the model considered enabled to demonstrate that the model possesses gyrotropic properties, i.e., it rotates on a polarization vector. Gyration constants are determined.     

限制卖空及带交易费用的证券组合的三参数模型

本文在 (Simaan(1993) )组合选择的三参数模型的框架下 ,考虑了交易费用 ,限制卖空 ,提出了新的风险证券投资组合模型 ,并给出了风险投资最优比例的算法 .     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

Time-irreversibility is hidden within Newtonian mechanics

ABSTRACT

We develop a bit-reversible implementation of Milne's fourth-order predictor algorithm so as to generate precisely time-reversible simulations of irreversible processes. We apply our algorithm to the collision of two zero-temperature Morse-potential balls, which collide to form a warm liquid oscillating drop. The oscillations are driven by surface tension and damped by the viscosities. We characterise the ‘important’ Lyapunov-unstable particles during the collision and equilibration phases in both time directions to demonstrate the utility of the Milne algorithm in exposing ‘Time's Arrow’.     

Maximizing the Product of Two Linear Functions In 0-1 Variables

We study both the continuous and discrete problems of maximizing the product of two linear functions subject to all variables being between 0 and 1. We first give linear and low-order polynomial algorithms for the solution of the continuous problem. In addition, we describe penalties that help to fix variables in the discrete problem. Extensive computational tests demonstrate the effectiveness of these results.     

On some auxiliary mappings generated by nonexpansive and strictly pseudo-contractive mappings

Starting by a finite family of mappings, we define the concept of procedure with Lipschitzian dependence of the coefficients. We give seven concrete examples of such procedures and prove the strong convergence of two viscosity methods.     

Beyond Black-Scholes: semimartingales and Lévy processes for option pricing

We consider the problem of option pricing when the underlying asset follows a general semimartingale process. After reviewing the foundations of arbitrage pricing theory for semimartingales and the link with Lévy processes, we introduce a general method to price options in this framework based on Fourier and Wavelet analysis. Received 4 September 2000     

基于遗传算法的生产批量优化问题

本文针对生产费用、生产准备费用和库存费用综合指标最小的最优的能力约束生产批量问题,建立基于遗传算法的数学模型,通过模拟试验及实际问题的计算验证了算法的可行性。