水灾地区邮递员问题

本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题,并对解的存在性给出了一系列的充分条件、必要条件及充要条件,得到了求解该问题的一个多项式算法。     

关于中国邮递员问题研究和发展的历史回顾

中国邮递员问题是运筹学研究的基本问题之一. 回顾了中国邮递员问题提出和解决的历史,同时,介绍了对此问题研究的发展概况.     

战争地区邮递员问题

本文首次提出了赋权有向图上中国邮递员问题的一个推广－战争地区邮递员问题，并对解的存在性给出了若干充分条件和必要条件，得到了求解该问题的一个多项式算法。     

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O（n³）的近似算法,将性能比从3/2改进到5/4.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...     

离线k-服务器问题算法的改进

阐述了在k-服务器猜想的证明中改进经典的离线k-服务器问题算法的必要性,从而对经典算法进行了改进,设计了一种新算法,其复杂度由原来的O(m(nk)2)下降为O(mk2).     

复合并行机F''''2|m1≥2,m2=1|Cmax排序问题的归并算法研究

在文献[1]中,已经证明了排序问题F2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F'2|m1≥2,m2=1|Cmax排序问题的一个启发式算法--归并算法,并证明了该算法在最坏情况下的性能比(Performance Ratio)是2m-1/m,且优于文献[2]中算法.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

二阶数乘问题的一个最优算法

研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下：给定n≥2个正整数a_1,a_2,…,a_n,设π为{1,2,…,n}的一个置换,表示该问题的一个解,试图找到一个置换π以至∑_（i=1）~n a_（π_i）a_（π_（i＋1））最小,在这里π_（n＋1）=π_1.给出了一个算法复杂度为O（n log n）的最优算法.     

On the max‐cut problem for a planar,cubic, triangle‐free graph,and the Chinese postman problem for a planar triangulation

Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 ? 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006     

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C₁,…,C_k} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width.     

Worst-case analysis of the differencing method for the partition problem

We prove that the worst-case performance ratio of the Karmarkar-Karp differencing method for the Partition Problem is 7/6     

Gilmore-Lawler bound of quadratic assignment problem

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.      

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

A TWO-STAGE SEMI-HYBRID FLOWSHOP PROBLEM IN GRAPHICS PROCESSING

In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)