A two-phase algorithm for the biobjective integer minimum cost flow problem

We present an algorithm to compute a complete set of efficient solutions for the biobjective integer minimum cost flow problem. We use the two phase method, with a parametric network simplex algorithm in phase 1 to compute all non-dominated extreme points. In phase 2, the remaining non-dominated points (non-extreme supported and non-supported) are computed using a k best flow algorithm on single-objective weighted sum problems.     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.     

A clustering method combining differential evolution with the K-means algorithm

The present paper considers the problem of partitioning a dataset into a known number of clusters using the sum of squared errors criterion (SSE). A new clustering method, called DE-KM, which combines differential evolution algorithm (DE) with the well known K-means procedure is described. In the method, the K-means algorithm is used to fine-tune each candidate solution obtained by mutation and crossover operators of DE. Additionally, a reordering procedure which allows the evolutionary algorithm to tackle the redundant representation problem is proposed. The performance of the DE-KM clustering method is compared to the performance of differential evolution, global K-means method, genetic K-means algorithm and two variants of the K-means algorithm. The experimental results show that if the number of clusters K is sufficiently large, DE-KM obtains solutions with lower SSE values than the other five algorithms.     

Optimality and stability of the K-hyperline clustering algorithm

K-hyperline clustering is an iterative algorithm based on singular value decomposition and it has been successfully used in sparse component analysis. In this paper, we prove that the algorithm converges to a locally optimal solution for a given set of training data, based on Lloyd’s optimality conditions. Furthermore, the local optimality is shown by developing an Expectation-Maximization procedure for learning dictionaries to be used in sparse representations and by deriving the clustering algorithm as its special case. The cluster centroids obtained from the algorithm are proved to tessellate the space into convex Voronoi regions. The stability of clustering is shown by posing the problem as an empirical risk minimization procedure over a function class. It is proved that, under certain conditions, the cluster centroids learned from two sets of i.i.d. training samples drawn from the same probability space become arbitrarily close to each other, as the number of training samples increase asymptotically.     

Probabilistic tree-based representation for solving minimum cost integer flow problems with nonlinear non-convex cost functions

The minimum cost flow problem (MCFP) is the most generic variation of the network flow problem which aims to transfer a commodity throughout the network to satisfy demands. The problem size (in terms of the number of nodes and arcs) and the shape of the cost function are the most critical factors when considering MCFPs. Existing mathematical programming techniques often assume the cost functions to be linear or convex. Unfortunately, the linearity and convexity assumptions are too restrictive for modelling many real-world scenarios. In addition, many real-world MCFPs are large-scale, with networks having a large number of nodes and arcs. In this paper, we propose a probabilistic tree-based genetic algorithm (PTbGA) for solving large-scale minimum cost integer flow problems with nonlinear non-convex cost functions. We first compare this probabilistic tree-based representation scheme with the priority-based representation scheme, which is the most commonly-used representation for solving MCFPs. We then compare the performance of PTbGA with that of the priority-based genetic algorithm (PrGA), and two state-of-the-art mathematical solvers on a set of MCFP instances. Our experimental results demonstrate the superiority and efficiency of PTbGA in dealing with large-sized MCFPs, as compared to the PrGA method and the mathematical solvers.     

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities.     

结合调整差值变换的(K,N)有意义图像分存方案

目的 针对传统有意义分存方法存在的像素扩张和分发掩体图像视觉质量不高等问题,提出一种结合调整差值变换的(K,N)有意义图像分存方案,该方案可用于与掩体等大且同为自然图像的密图分存.方法 在分存阶段,首先用调整差值变换将密图转换为差值图和位置图;其次将差值图和位置图进行(K,N)分存,分别嵌入到掩体图像中,并使用密钥确定位置图分存信息的嵌入位置和根据位置图中不同的差值类型选择不同的差值嵌入方法;再次对密钥进行(K,N)分存,将子密钥和分发掩体对应的MD5值公布到第3方公信方作为认证码;最后将子密钥和分发掩体分发给参与者进行保管.在恢复阶段,首先核对参与者的子密钥和分发掩体对应的MD5值,若认证通过的人数小于K,则恢复失败;否则,使用认证通过的子密钥还原出密钥,然后根据密钥提取并恢复出位置图;其次根据位置图中的差值类型来提取和恢复出差值图;最后使用逆调整差值变换还原出最终密图.结果 同现有方法相比,所提策略不存在像素扩张且分发掩体图像视觉质量较高,具有较强的恶意参与者检测能力.结论 本文方法的掩体图像与密图等大且同为自然图像,同经典有意义图像分存方案相比,克服了像素扩张问题,嵌入信息后的掩体图像具有较高的视觉质量,使用第3方公信方存储的MD5值作为认证码,具有较强的恶意参与者识别能力.     

The biobjective integer minimum cost flow problem—incorrectness of Sedeño-Noda and Gonzàlez-Martin's algorithm

In this paper, we show with a counterexample, that the method proposed by Sedeño-Noda and Gonzàlez-Martin for the biobjective integer minimum flow problem is not able to find all efficient integer points in objective space.     

Minimal-cost network flow problems with variable lower bounds on arc flows

The minimal-cost network flow problem with fixed lower and upper bounds on arc flows has been well studied. This paper investigates an important extension, in which some or all arcs have variable lower bounds. In particular, an arc with a variable lower bound is allowed to be either closed (i.e., then having zero flow) or open (i.e., then having flow between the given positive lower bound and an upper bound). This distinctive feature makes the new problem NP-hard, although its formulation becomes more broadly applicable, since there are many cases where a flow distribution channel may be closed if the flow on the arc is not enough to justify its operation. This paper formulates the new model, referred to as MCNF-VLB, as a mixed integer linear programming, and shows its NP-hard complexity. Furthermore, a numerical example is used to illustrate the formulation and its applicability. This paper also shows a comprehensive computational testing on using CPLEX to solve the MCNF-VLB instances of up to medium-to-large size.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

Bee colony optimization for the p-center problem

Bee colony optimization (BCO) is a relatively new meta-heuristic designed to deal with hard combinatorial optimization problems. It is biologically inspired method that explores collective intelligence applied by the honey bees during nectar collecting process. In this paper we apply BCO to the p-center problem in the case of symmetric distance matrix. On the contrary to the constructive variant of the BCO algorithm used in recent literature, we propose variant of BCO based on the improvement concept (BCOi). The BCOi has not been significantly used in the relevant BCO literature so far. In this paper it is proved that BCOi can be a very useful concept for solving difficult combinatorial problems. The numerical experiments performed on well-known benchmark problems show that the BCOi is competitive with other methods and it can generate high-quality solutions within negligible CPU times.     

A de-texturing and spatially constrained K-means approach for image segmentation

This paper presents a new and simple segmentation method based on the K-means clustering procedure and a two-step process. The first step relies on an original de-texturing procedure which aims at converting the input natural textured color image into a color image, without texture, that will be easier to segment. Once, this de-textured (color) image is estimated, a final segmentation is achieved by a spatially-constrained K-means segmentation. These spatial constraints help the iterative K-means labeling process to succeed in finding an accurate segmentation by taking into account the inherent spatial relationships and the presence of pre-estimated homogeneous textural regions in the input image. This procedure has been successfully applied on the Berkeley image database. The experiments reported in this paper demonstrate that the proposed method is efficient (in terms of visual evaluation and quantitative performance measures) and performs competitively compared to the best existing state-of-the-art segmentation methods recently proposed in the literature.     

Tight bounds on the number of minimum-mean cycle cancellations and related results

We prove a tight (min(nm log(nC), nm²)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations toO(nm ²). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm²) iterations.Partially supported by NSF Presidential Young Investigator Grant CCR-8858097 with matching funds provided by AT&T, IBM Faculty Development Award, and a grant from the 3M Corporation.     

On finding representative non-dominated points for bi-objective integer network flow problems

This paper proposes a new algorithm to find a representation of the set of all non-dominated points of the bi-objective integer network flow problem. The algorithm solves a sequence of ε-constraint problems with a branch-and-bound algorithm to find a subset of non-dominated points that represents the set of all non-dominated points well in the sense of coverage or uniformity. At each iteration of the algorithm, one non-dominated point, determined by solving one ε-constraint problem, is added to the representation until it is guaranteed that the representation has the desired quality. Computational experiments on different problem types show the efficacy of the algorithm.     

An algorithm for ranking assignments using reoptimization

We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Its computational performance is compared with all available implementations of algorithms with the same time complexity. The results are encouraging.