带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

基于博弈论的节能量保证型EPC合同决策分析

合同能源管理(EPC)是一种以未来节约的能源费用支付节能项目成本的节能管理机制。节能量保证型EPC模式中,耗能企业负责为项目融资,节能服务公司提供项目的全程服务并向客户企业保证一定的节能效益。若达不到承诺值,节能服务公司向客户进行补偿,若超出承诺值,客户给予节能服务公司一定的奖励。合同决策问题是该模式应用中的重要问题。本文以节能量保证型EPC合同中初始项目投资、合同期限和超额节能效益奖励的决策问题为研究对象,建立了客户和节能服务公司之间的决策博弈模型,分析二者的最优合同决策。数值试验结果表明,该方法不仅能让客户企业和节能服务公司均受益,还可以有效提高项目的投资报酬率,并且较高的节能服务公司技术水平和客户初始耗能水平能产生更高的节能效率。     

修约间隔规则与回归系数的有效位数

从微小标准偏差准则导出独立测量结果修约间隔的确定规则.考虑回归系数之间强相关性,系数不确定度的有效位数常常需要保留到两位以上.引入有效修约间隔,导出回归系数修约间隔的确定公式,结合实验物理中的多种不同回归类型例子说明了回归系数的有效位数确定方法.     

Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm.The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels.     

Integer matrices with constraints on leading partial row and column sums

Consider the problem of finding an integer matrix that satisfies given constraints on its leading partial row and column sums. For the case in which the specified constraints are merely bounds on each such sum, an integer linear programming formulation is shown to have a totally unimodular constraint matrix. This proves the polynomial-time solvability of this case. In another version of the problem, one seeks a zero-one matrix with prescribed row and column sums, subject to certain near-equality constraints, namely, that all leading partial row (respectively, column) sums up through a given column (respectively, row) are within unity of each other. This case admits a polynomial reduction to the preceding case, and an equivalent reformulation as a maximum-flow problem. The results are developed in a context that relates these two problems to consistent matrix rounding.     

On Rounding Error Sums Related to the Circle Problem. ii

For a positive real parameter t, real numbers , , and , we consider sums , where is the rounding error function, i.e.\ . Generalizing and improving the main result of Part I of the paper we show that there exists an absolute constant such that for all , and all . Further, we give applications concerning the circle problem with linear, polynomial, and general weight.     

Rapid multiplication modulo the sum and difference of highly composite numbers

We extend the work of Richard Crandall et al. to demonstrate how the Discrete Weighted Transform (DWT) can be applied to speed up multiplication modulo any number of the form where is small. In particular this allows rapid computation modulo numbers of the form .

In addition, we prove tight bounds on the rounding errors which naturally occur in floating-point implementations of FFT and DWT multiplications. This makes it possible for FFT multiplications to be used in situations where correctness is essential, for example in computer algebra packages.

     

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory's fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the global validity of classical cuts after branching has occurred are derived. Work supported in part by a grant from the Office of Naval Research (N00014-96-0327). Reprinted from Math. Meth. Oper. Res. (2001) 53, 173–203.     

Efficient and stable solution of structured Hessenberg linear systems arising from difference equations

This paper is concerned with the efficient solution of (block) Hessenberg linear systems whose coefficient matrix is a Toeplitz matrix in (block) Hessenberg form plus a band matrix. Such problems arise, for instance, when we apply a computational scheme based on the use of difference equations for the computation of many significant special functions and quantities occurring in engineering and physics. We present a divide‐and‐conquer algorithm that combines some recent techniques for the numerical treatment of structured Hessenberg linear systems. Our approach is computationally efficient and, moreover, in many practical cases it can be shown to be componentwise stable. Copyright © 2000 John Wiley & Sons, Ltd.     

一次同余组的关键因子求解算法

本文在文 [1 ]的基础上定义了关键因子的概念 ,提出了一次同余组的关键因子求解算法 ,并给出了解的舍入误差估计 .通过实例说明了该算法的求解过程 ,分析了该算法在计算机求解时相对于传统解法的优点 .