三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

The directed profitable location Rural Postman Problem

In this paper we introduce an extension of the well known Rural Postman Problem, which combines arc routing with profits and facility location. Profitable arcs must be selected, facilities located at both end-points of the selected arcs, and a tour identified so as to maximize the difference between the profit collected along the arcs and the cost of traversing the arcs and installing the facilities. We analyze properties of the problem, present a mathematical programming formulation and a branch-and-cut algorithm. In an extensive computational experience the algorithm could solve instances with up to 140 vertices and 190 arcs and up to 50 vertices and 203 arcs.     

Lower bounds and heuristics for the Windy Rural Postman Problem

In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.     

New results for the Directed Profitable Rural Postman Problem

We study a generalization of the Directed Rural Postman Problem where not all arcs requiring a service have to be visited provided that a penalty cost is paid if a service arc is not crossed. The problem, known as Directed Profitable Rural Postman Problem, looks for a tour visiting the selected set of service arcs while minimizing both traveling and penalty costs. We add different valid inequalities to a known mathematical formulation of the problem and develop a branch-and-cut algorithm that introduces connectivity constraints both in a “lazy” and in a standard way. We also propose a matheuristic followed by an improvement heuristic (final refinement). The matheuristic exploits information provided by a problem relaxation to select promising service arcs used to solve optimally Directed Rural Postman problems. The ex-post refinement tries to improve the solution provided by the matheuristic using a branch-and-cut algorithm. The method gets a quick convergence through the introduction of connectivity cuts that are not guaranteed to be valid inequalities, and thus may exclude integer feasible solutions.     

Polynomial Time Approximation Scheme for Symmetric Rectilinear Steiner Arborescence Problem

The Symmetric Rectilinear Steiner Arborescence (SRStA) problem is defined as follows: given a set of terminals in the positive quadrant of the plane, connect them using horizontal and vertical lines such that each terminal can be reached from the origin via a y-monotone path and the total length of all the line segments is the minimum possible. Finding an SRStA has applications in VLSI design, in data structures used in some optimization algorithms and in dynamic server problems. In this paper, we provide a polynomial time approximation scheme for the SRStA problem, improving the previous best approximation ratio of 3 for this problem.     

The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard,yet disconnectedness is manageable

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.     

A branch-and-cut algorithm for the Undirected Rural Postman Problem

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported. Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000     

关于对偶Steiner多项式的根的注记

受凸体的Steiner多项式的启发,定义了星体的对偶Steiner多项式,并利用对偶Aleksandrov-Fenchel不等式讨论了对偶Steiner多项式的根.进而,得到了关于对偶Steiner多项式的根的一些不等式,这些不等式恰好是关于Steiner多项式的根的不等式的对偶形式.     

Formulating and Solving the Minimum Dominating Cycle Problem

This paper introduces a formulation for the Minimum Dominating Cycle Problem. Additionally, a Branch and Cut algorithm, based on that formulation, is also investigated. So far, the algorithm contains no primal heuristics. However, it managed to solve to proven optimality, in acceptable CPU times, all test instances with up to 120 vertices.     

关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题．通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案．     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.