On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

基于数据压缩的LSP参数高效量化算法

文中为解决超长帧编码系统中联合帧数过多导致LSP参数量化性能下降这个问题,将多项式拟合引入超长帧编码系统中,利用多项式拟合压缩LSP参数矩阵,以降低量化时实际联合的帧数。再用分裂矩阵量化器进行量化。仿真结果表明,在120 bps的参数量化速率下,此算法的量化性能优于矩阵量化算法(MQ),平均谱失真比MQ算法降低了0.0719 dB,平均分段信噪比提高了0.1971 dB。     

The building evacuation problem with shared information

In this article, the Building Evacuation Problem with Shared Information (BEPSI) is formulated as a mixed integer linear program, where the objective is to determine the set of routes along which to send evacuees (supply) from multiple locations throughout a building (sources) to the exits (sinks) such that the total time until all evacuees reach the exits is minimized. The formulation explicitly incorporates the constraints of shared information in providing online instructions to evacuees, ensuring that evacuees departing from an intermediate or source location at a mutual point in time receive common instructions. Arc travel time and capacity, as well as supply at the nodes, are permitted to vary with time and capacity is assumed to be recaptured over time. The BEPSI is shown to be NP‐hard. An exact technique based on Benders decomposition is proposed for its solution. Computational results from numerical experiments on a real‐world network representing a four‐story building are given. Results of experiments employing Benders cuts generated in solving a given problem instance as initial cuts in addressing an updated problem instance are also provided. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Simple paths with exact and forbidden lengths

We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested.     

分布式系统设计中的互斥问题

介绍了互斥问题的基本概念,并针对分布式系统设计中的互斥问题分析了非基于令牌和基于令牌的两种解决方案.通过对典型算法的分析,有助于对分布式系统形成可操作的数学模型.     

A partial characterization of the optimal ordering/rationing policy for a periodic review system with two demand classes and backordering

We consider a finite horizon periodic review, single product inventory system with a fixed setup cost and two stochastic demand classes that differ in their backordering costs. In each period, one must decide whether and how much to order, and how much demand of the lower class should be satisfied. We show that the optimal ordering policy can be characterized as a state dependent (s,S) policy, and the rationing structure is partially obtained based on the subconvexity of the cost function. We then propose a simple heuristic rationing policy, which is easy to implement and close to optimal for intensive numerical examples. We further study the case when the first demand class is deterministic and must be satisfied immediately. We show the optimality of the state dependent (s,S) ordering policy, and obtain additional rationing structural properties. Based on these properties, the optimal ordering and rationing policy for any state can be generated by finding the optimal policy of only a finite set of states, and for each state in this set, the optimal policy is obtained simply by choosing a policy from at most two alternatives. An efficient algorithm is then proposed. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

原始变量守恒形式控制方程的时间准确性分析

基于压力、速度和温度的原始变量为自变量的守恒形式的控制方程可应用于定常流动问题，但是在求解非定常问题，例如某一典型激波管问题时，激波后温度出现过冲现象，即使通过细化网格、提高空间格式精度或者换用其他通量格式仍不能消除，这表明误差可能来自该方法本身。采用一维Euler方程对该方法进行数值分析。分析结果表明，数值误差来自时间项。通过构造相应的双时间步方程，虚拟时间项采用原始变量，而物理时间项采用守恒变量，并在两个相邻物理时间步内作为定常问题求解，可以收敛到相应的守恒形式，消除上述误差，得到准确的非定常数值解。     

HLA和视景仿真技术的装甲车辆乘员协同训练系统

简单介绍了HLA/RTI的特点和功能,讨论了利用MultiGen Creator 和 Vega Prime建立三维模型时用到的关键技术,以及部分特效的实现技巧.并详细说明了分布式协同训练系统下的时间管理和数据分发管理的实现策略.给出了基于HLA/RTI和三维视景仿真技术下分布式协同训练系统的实现方法.     

Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand

We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by where κ₁, κ₂ are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature.