On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming

In a communication network one often needs to combine several communication requests into a path in a physical layer of the network. In these cases the cost is measured in terms of the total length of these paths or the total hardware cost of maintaining these paths. In this paper we consider a problem belonging to this general family of optimization problems. We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d=1 the problem is APX-hard, i.e. a polynomial time approximation scheme for it does not exist (unless P=NP). On the other hand, we solve such a problem for general G and any d and g, by providing an O(logg)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g.     

Optimizing Insertions in a Constraint Routing Problem with Complicated Cost Functions

Journal of Computer and Systems Sciences International - An iterative method for solving routing problems subject to constraints and possible dependence of the cost functions on the list of tasks...     

最小生成树算法在旅行商问题中的应用

如何在n个顶点之间的1/2(n-1)!巡回路径中选择距离最短的,这是一个典型的组合优化问题,也是解决旅行商问题的根本。在最小生成树的基本思想上进行了改进,成功地解决了旅行商问题。     

On the History of the Minimum Spanning Tree Problem

It is standard practice among authors discussing the minimum spanning tree problem to refer to the work of Kruskal(1956) and Prim (1957) as the sources of the problem and its first efficient solutions, despite the citation by both of Boruvka (1926) as a predecessor. In fact, there are several apparently independent sources and algorithmic solutions of the problem. They have appeared in Czechoslovakia, France, and Poland, going back to the beginning of this century. We shall explore and compare these works and their motivations, and relate them to the most recent advances on the minimum spanning tree problem.     

哈夫曼树的实现及其在文件压缩中的应用

在信息快速传输和存储的过程中,数据压缩有着非常重要的作用.介绍了基于哈夫曼树的文本压缩和解压缩的原理与方法,并给出了Huiffman压缩与解压程序核心算法的实现过程.     

对哈夫曼树唯一性的探讨

在我们的日常教学中,我们经常会对哈夫曼树的建立给出不同答案,那么是否有唯一标准答案?通过相关程序流程及代码实验,分析了导致认为创建哈夫曼树不唯一的原因,说明了在一种既定的算法下,我们是可以达到哈夫曼树建立的唯一性的.     

On the Value Functions of the Discrete-Time Switched LQR Problem

In this paper, we derive some important properties for the finite-horizon and the infinite-horizon value functions associated with the discrete-time switched LQR (DSLQR) problem. It is proved that any finite-horizon value function of the DSLQR problem is the pointwise minimum of a finite number of quadratic functions that can be obtained recursively using the so-called switched Riccati mapping. It is also shown that under some mild conditions, the family of the finite-horizon value functions is homogeneous (of degree 2), is uniformly bounded over the unit ball, and converges exponentially fast to the infinite-horizon value function. The exponential convergence rate of the value iterations is characterized analytically in terms of the subsystem matrices.      

基于霍夫曼树和逆云模型的雷达拖引干扰识别

针对噪声环境中雷达干扰正确识别率较低的问题,提出了一种新的基于霍夫曼树和逆云模型联合的雷达欺骗干扰识别方法.该方法首先利用干扰数据库,提取有效的识别特征参数库,然后基于霍夫曼树建立识别模型.在每个节点,利用基于逆云模型的隶属度分类,实现待测干扰的识别.仿真结果表明,与传统的干扰识别方法相比,该识别方法能很好地应对雷达干扰的随机性和模糊性,能在干扰参数数值区间有重叠时有效识别雷达干扰.     

带有时间和费用限制的网络容量扩充问题

研究了带有时间和费用双重限制下的网络容量扩充问题,即在满足时间和费用约束条件下,如何扩充网络中某些弧的容量使扩充后的网络容量尽可能的夫。通过将问题转化为求其最小生成树,给出了其求解算法。由于在扩充时两个约束条件一般有一者剩余,为了合理配置扩充资源,讨论了给定容量要求F关于时间和费用的Parclo优化解的情况并给出了有效算法,用实例来证明了算法的有效性。     

电子商务中有时间窗物流配送路径优化研究

电子商务物流企业面临的是多批次、小批量、时间要求高、需求个性化的现代化市场,为了提高模型的适用性和通用性,将传统车辆调度模型进行修改,将目标函数改为基于费用最小,在约束条件中增加最大工作时间、多类车型、车辆载重量限制和最大行驶距离。由于有时间窗的车辆调度问题是NP难问题,采用改进两阶段算法进行求解。即第一阶段用K-means将客户群分成若干区域;第二个阶段对各个分组内客户点,就是一个个单独TSPTW模型的线路优化问题,采用混合遗传算法进行优化求解,最后,结合具体实例,证明该改进算法的良好性能。     

The Stable Roommates Problem with Choice Functions

The stable marriage theorem of Gale and Shapley states that for n men and n women there always exists a stable marriage scheme, that is, a set of marriages such that no man and woman mutually prefer one another to their partners. The stable marriage theorem was generalized in two directions: the stable roommates problem is the “one-sided” version, where any two agents on the market can form a partnership. The generalization by Kelso and Crawford is in the “two-sided” model, but on one side of the market agents have a so-called substitutable choice function, and stability is interpreted in a natural way. It turned out that even if both sides of the market have substitutable choice functions, there still exists a stable assignment. The latter version contains the “many-to-many” model where up to a personal quota, polygamy is allowed for both men and women in the two-sided market.     

带测度函数的连通支配集问题

连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题（CDS（F））,使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的NP完全性,并给出多项式时间的近似算法,它的近似度为Ln△＋3（△为图中顶点的最大度数）。     

Online Unweighted Knapsack Problem with Removal Cost

In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u ₁,u ₂,…,u _n , each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u _i , we either put u _i into the knapsack or reject it with no cost. When u _i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u _i and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred. In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible.     

带有时间和费用双重限制的网络容量扩充问题

该文将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题的一般模型。通过网络变换,将带有时间限制的容量扩充问题转化为线性最小费用流问题,并给出了具体证明和求解容量扩充问题的算法。该模型和算法不仅适用于各种情形的容量扩充问题,而且还可应用于网络流规划。最后通过具体例子的求解,说明了模型和算法的正确性和有效性。     

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题（ＲＭＳＴ）的模型,并证明该问题是ＮＰ－完全的。利用经典Ｇｒｅｅｄｙ算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。     

On Exact Solutions for the Rectilinear Steiner Tree Problem Part I: Theoretical Results

The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithms for this problem are based on dynamic programming and have a running time of O(n ² . . . 2.62 ⁿ ) (Ganley and Cohoon), resp. (Smith). The first algorithm can solve problems of size 27, the second one is highly impractical because of the large constant in the exponent. The best implementations perform poorly even on small problem instances; the best practical results can be reached using a Branch \& Bound approach (Salowe and Warme); this implementation can solve random problems of size 35 within a day, while the dynamic programming approach of Ganley and Cohoon can handle only 27 point examples. In this paper we improve the theoretical worst-case time bound to O(n ² . . . 2.38 ⁿ ) , for random problem instances we prove a running time of α ⁿ with a constant α < 2 . We have implemented our algorithms and can now solve problems of 40 points in a day using a provably good dynamic programming approach, and can solve problems of 55 points with a Branch \& Bound strategy. For exponential-time algorithms, this is an enormous improvement. Received April 2, 1997; revised January 5, 1998.     

斐波那契树优化算法求解多峰函数全局最优解的可达性分析

为分析和验证斐波那契树优化算法（Fibonacci tree optimization algorithm,FTO）求解多峰函数全局最优解的算法性能,对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构,在搜索空间中进行全局、局部交替搜索,不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验,分析和验证了算法求解多峰函数全局最优解的可达性.     

考虑能耗成本和拖期成本的非同等并行机调度

针对橡胶轮胎硫化车间能源消耗大,浪费严重的现象,提出一类考虑能耗成本与拖期成本的非等同并行机调度问题,建立基于硫化机正常运行、空闲、停机三种运行状态的能源消耗成本与拖期成本的调度模型。设计了基于优先调度规则的启发式算法、基于能耗优化的启发式算法、组合启发式算法用于模型求解,并通过仿真实验分析、比较了各种算法的有效性与适用环境。同时,仿真实验结果也表明本文提出的考虑能耗成本和拖期成本的非同等并行机调度问题具有一定的理论与实践意义。     

图的steiner最小树问题及其求解

斯坦纳树问题是组合优化学科中的一个问题。属于NP-难问题,即无法在多项式时间内得到最优解。本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。最后对算法进行了分析。