Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

In this paper the problem of optimally guillotine cutting a rectangle (A, B  ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,_ai),i∈I$(c\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in J$ have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.     

A comparison of two algorithms for the assignment problem

State-of-the-art computational results have shown that the shortest augmenting path (SAP) methods are more efficient than other primal-dual and primal-simplex based methods for solving the linear assignment problem on uniprocessor computers. There is, however, some controversy concerning their merits when compared with Bertsekas' auction algorithm on multiprocessor computers. In this study we investigate the performance of these competing methods on the Alliant FX/8. For each method, theoretical motivation, sources of parallelism and computational results are presented.     

New models for shortest path problem with fuzzy arc lengths

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.     

Models and algorithms for the reconfiguration of distributed wireless switching systems

This paper is a summary of the author’s PhD thesis entitled “Models and algorithms for the reconfiguration of wireless switching systems”. The thesis deals with the study of a strongly NP-hard resource-constrained scheduling problem arising from the telecommunication industry. This work was supervised by Jacques Carlier and Dritan Nace, both from Université de Technologie de Compiègne, and carried out while the author was a System Architect within Nortel GSM Access R&D organization. The thesis, which is written in both French and English, has been defended on 29 March 2007 and is available by email request to the author. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

Efficient algorithms for the 2-Way Multi Modal Shortest Path Problem

We consider the 2-Way Multi Modal Shortest Path Problem (2WMMSPP). Its goal is to find two multi modal paths with total minimal cost, an outgoing path and a return path. The main difficulty lies in the fact that if a private car or bicycle is used during the outgoing path, it has to be picked up during the return path. The shortest return path is typically not equal to the shortest outgoing path as traffic conditions and timetables of public transportation vary throughout the day. In this paper we propose an efficient algorithm based on bi-directional search and provide experimental results on a realistic multi modal transportation network.     

Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network

This paper investigates the solution algorithms for the multi-criteria multi-modal shortest path problem (M-SPP), which belongs to the set of problems known as NP-hard, in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on). To get their destination, the passengers can alternate between different modes. As a special demand, the time-window is usually associated with the M-SPP. Because of the service time-limit of modes, the available modes at a stop are varied with the time. So the optimal M-SPP with arriving time-window cannot be simply obtained by finding the optimal M-SPP firstly and then reversely deducing the leaving time-window of the origin according to the arriving time-window of destination. In this paper, the M-SPP with arriving time-window is firstly proposed. To solve the multi-criteria M-SPPs (MM-SPP) with transfer delaying, an improved exact label correcting algorithm (LCA) is designed and, to solve the proposed MM-SPPs with both of transfer delaying and arriving time-window, an exact reverse LCA is designed. Finally, some computing examples are given to test the effectiveness of the designed algorithms.     

Empirical Gramian-based spatial basis functions for model reduction of nonlinear distributed parameter systems

Correct selection of spatial basis functions is crucial for model reduction for nonlinear distributed parameter systems in engineering applications. To construct appropriate reduced models, modelling accuracy and computational costs must be balanced. In this paper, empirical Gramian-based spatial basis functions were proposed for model reduction of nonlinear distributed parameter systems. Empirical Gramians can be computed by generalizing linear Gramians onto nonlinear systems, which results in calculations that only require standard matrix operations. Associated model reduction is described under the framework of Galerkin projection. In this study, two numerical examples were used to evaluate the efficacy of the proposed approach. Lower-order reduced models were achieved with the required modelling accuracy compared to linear Gramian-based combined spatial basis function- and spectral eigenfunction-based methods.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

Approximation algorithms for the test cover problem

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics. Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Partially supported by a Merck Computational Biology and Chemistry Program Graduate Fellowship from the Merck Company Foundation.Also Iceland Genomics CorporationPartially supported by subcontract No. 16082-RFP-00-2C in the area of ``Combinatorial Optimization in Biology (XAXE),' Los Alamos National Laboratories, and NSF grant CCR-0105548.Mathematics Subject Classification: 90B27     

A two step algorithm for solving a large scale semi-definite logit model

This paper proposes a two step algorithm for solving a large scale semi-definite logit model, which is appreciated as a powerful model in failure discriminant analysis. This problem has been successfully solved by a cutting plane (outer approximation) algorithm. However, it requires much more computation time than the corresponding linear logit model. A two step algorithm to be proposed in this paper is intended to reduce the amount of computation time by eliminating a certain portion of the data based on the information obtained by solving an associated linear logit model. It will be shown that this algorithm can generate a solution with almost the same quality as the solution obtained by solving the original large scale semi-definite model within a fraction of computation time.     

Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the “asymptotic transfers,” which roughly bridges the asymptotics of the “conquering cost of the subproblems” and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms.     

Genetic algorithms for the selection of smoothing parameters in additive models

Summary  Additive models of the type y=f ₁(x ₁)+...+f _p(x _p)+ε where f _j , j=1,..,p, have unspecified functional form, are flexible statistical regression models which can be used to characterize nonlinear regression effects. One way of fitting additive models is the expansion in B-splines combined with penalization which prevents overfitting. The performance of this penalized B-spline (called P-spline) approach strongly depends on the choice of the amount of smoothing used for components f _j . In particular for higher dimensional settings this is a computationaly demanding task. In this paper we treat the problem of choosing the smoothing parameters for P-splines by genetic algorithms. In several simulation studies this approach is compared to various alternative methods of fitting additive models. In particular functions with different spatial variability are considered and the effect of constant respectively local adaptive smoothing parameters is evaluated.     

From how to why: A quest for the common mathematical meanings behind two different division algorithms

During their education cycle in mathematics, students are exposed to algorithms as early as primary school. Several studies show how students frequently learn to perform these algorithms without controlling the mathematical meanings behind them. On the other hand, several National Standards have highlighted the need to construct meanings in mathematics from the first cycle of education. In this paper we focus on division algorithms, investigating to what extent 6th graders can be guided to understanding the whys behind an algorithm, through the comparison of two different algorithms for integer division. Our results suggest, on the one hand, that “it could work!”, and on the other hand, that the exposure to different algorithms for the same mathematical operation seems particularly significant for bringing out the whys behind such algorithms, as well as for capturing the difference between a mathematical operation and algorithms for calculating the result of such an operation.     

比例风险模型下参数估计的两种MM算法的一些应用

对于带有删失机制的生存数据的研究,比例风险模型是应用最为广泛的统计模型之一。实际中,为得到其参数的极大似然估计需要采用数值方法计算得分方程的解。MinorizationMaximization算法(以下简称"MM算法")将求解复杂的目标函数的极值问题转化为求解简单的代理函数的极值问题。本文主要探讨,在比例风险模型下通过两种不同的思想为偏似然函数构造代理函数,从而得到的两种MM算法。通过数值模拟和实际数据分析实现这两种MM算法在比例风险模型下的一些应用。     

Optimal investment strategy for asset-liability management under the Heston model

ABSTRACT

This paper focuses on an asset-liability management problem for an investor who can invest in a risk-free asset and a risky asset whose price process is governed by the Heston model. The objective of the investor is to find an optimal investment strategy to maximize the expected exponential utility of the surplus process. By using the stochastic control method and variable change techniques, we obtain a closed-form solution of the corresponding Hamilton–Jacobi–Bellman equation. We also develop a verification theorem without the usual Lipschitz assumptions which can ensure that this closed-form solution is indeed the value function and then derive the optimal investment strategy explicitly. Finally, we provide numerical examples to show how the main parameters of the model affect the optimal investment strategy.     

偏正态数据下众数回归模型的统计诊断

为了更好地拟合偏态数据,充分提取偏态数据的信息,针对偏正态数据建立了众数回归模型,并基于Pena距离统计量对众数回归模型进行统计断研究,得到了众数回归模型的Pena距离表达式以及高杠杆异常点的诊断方法.利用EM算法与梯度下降法给出了众数回归模型参数的极大似然估计,根据数据删除模型计算似然距离、Cook距离和Pena距离统计量,绘制诊断统计图.通过Monte Carlo模拟试验和实例分析比较,说明文章提出的方法行之有效,并在一定条件下Pena距离对异常点或强影响点的诊断优于似然距离和Cook距离.     

A greedy algorithm for the two-level nested logit model

We consider the assortment optimization problem under the classical two-level nested logit model. We establish a necessary and sufficient condition for the optimal assortment and develop a simple and fast greedy algorithm that iteratively removes at most one product from each nest to compute an optimal solution.     

A bi-level programming model and solution algorithm for the location of logistics distribution centers

In this paper, by considering benefits of customers and logistics planning departments, a bi-level programming model is presented to seek the optimal location for logistics distribution centers. The upper-level model is to determine the optimal location by minimizing the planners’ cost, and the lower gives an equilibrium demand distribution by minimizing the customers’ cost. Based on the special form of constraints, a simple heuristic algorithm is proposed. Finally, a numerical example is used to illustrate the application of the method, which shows that the algorithm is feasible and advantageous.     

Statistical estimation for some dividend problems under the compound Poisson risk model

In this paper, we consider some dividend problems in the classical compound Poisson risk model under a constant barrier dividend strategy. Suppose that the Poisson intensity for the claim number process and the distribution for the individual claim sizes are both unknown. We use the COS method to study the statistical estimation for the expected present value of dividend payments before ruin and the expected discounted penalty function. The convergence rates under large sample setting are derived. Some simulation results are also given to show effectiveness of the estimators under finite sample setting.     

Existence of strong minimizers for the Griffith static fracture model in dimension two

We consider the Griffith fracture model in two spatial dimensions, and prove existence of strong minimizers, with closed jump set and continuously differentiable deformation fields. One key ingredient, which is the object of the present paper, is a generalization to the vectorial situation of the decay estimate by De Giorgi, Carriero, and Leaci. This is based on replacing the coarea formula by a method to approximate $SB{D}^p$ functions with small jump set by Sobolev functions, and is restricted to two dimensions. The other two ingredients will appear in companion papers and consist respectively in regularity results for vectorial elliptic problems of the elasticity type and in a method to approximate in energy $GSB{D}^p$ functions by $SB{V}^p$ ones.