用于JPEG2000图像认证的鲁棒性水印算法

针对JPEG2000图像压缩标准所具有的渐进传输、一次编码多次解码等特性,提出了一种基于图像特征的鲁棒性图像认证算法.该算法在JPEG2000编码过程中,先根据图像不变特征,生成认证水印,再根据实际的鲁棒性认证需求,在量化后的小波系数中确定每个子带的认证水印嵌入位平面,最后基于小波系数位平面的特征嵌入认证水印.算法不仅能适应JPEG2000各种灵活的编码方式,还能定位图像篡改的位置.实验结果验证了图像认证算法对可允许图像操作的鲁棒性以及对图像篡改的敏感性.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

The rectilinear distance Weber problem in the presence of a probabilistic line barrier

This paper considers the problem of locating a single facility in the presence of a line barrier that occurs randomly on a given horizontal route on the plane. The objective is to locate this new facility such that the sum of the expected rectilinear distances from the facility to the demand points in the presence of the probabilistic barrier is minimized. Some properties of the problem are reported, a solution algorithm is provided with an example problem, and some future extensions to the problem are discussed.     

The capacitated single-allocation hub location problem revisited: A note on a classical formulation

In this paper a well-known formulation for the capacitated single-allocation hub location problem is revisited. An example is presented showing that for some instances this formulation is incomplete. The reasons for the incompleteness are identified leading to the inclusion of an additional set of constraints. Computational experiments are performed showing that the new constraints also help to decrease the computational time required to solve the problem optimally.     

Probabilistic analysis of geometric location problems

We analyze the behaviour of thek center and median problems forn points randomly distributed in an arbitrary regionA ofR ^d . Under a mild assumption on the regionA, we show that fork≦k(n)=o(n/logn), the objective function values of the discrete and continuous versions of these problems are equal to each otheralmost surely. For the two-dimensional case, both these problems can be solved by placing the centers or medians in an especially simple regular hexagonal pattern (the ‘honeycomb heuristic’ of Papadimitriou). This yields the exact asymptotic values for thek center and median problem, namely, α(|A|/k)^1/2 and β(|A|/k)^1/2, where |A| denotes the volume ofA, α and β are known constants, and the objective of the median problem is given in terms of the average, rather than the usual total, distance. For the 3- and 4-dimensional case, similar results can be obtained for the center problem to within an accuracy of roughly one percent. As a by-product, we also get asymptotically optimal algorithms for the 2-dimensionalp-normk median problem and for the twin problems of minimizing the maximum number of vertices served by any center and similarly for maximizing the minimum.     

Competitive facility location model with concave demand

We consider a spatial interaction model for locating a set of new facilities that compete for customer demand with each other, as well as with some pre-existing facilities to capture the “market expansion” and the “market cannibalization” effects. Customer demand is assumed to be a concave non-decreasing function of the total utility derived by each customer from the service offered by the facilities. The problem is formulated as a non-linear Knapsack problem, for which we develop a novel solution approach based on constructing an efficient piecewise linear approximation scheme for the objective function. This allows us to develop exact and α-optimal solution approaches capable of dealing with relatively large-scale instances of the model. We also develop a fast Heuristic Algorithm for which a tight worst-case error bound is established.     

Spherical Minimax Location Problem

This paper presents an algorithm for determining a minimax location to service demand points that are equally weighted and distributed over a sphere. The norm under consideration is geodesic. The algorithm presented here is based on enumeration and has a polynomial time complexity.     

Global Optimization of 0-1 Hyperbolic Programs

We develop eight different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating ten restaurants in the city of Edmonton.The research was supported in part by NSF awards DMII 95-02722 and BES 98-73586 to NVS.     

Locating Multiple Competitive Facilities: Spatial Interaction Models with Variable Expenditures

We develop a new framework for location of competitive facilities by introducing non-constant expenditure functions into spatial interaction location models. This framework allows us to capture two key effects – market expansion and cannibalization – within the same model.We develop algorithmic approaches for finding optimal or near-optimal solutions for several models that arise from choosing a specific form of the expenditure functions.     

区域分工水平评价的新方法——区位结构熵法

根据区域产业分工理论,运用区位商测定区域专业化程度.然后,基于复杂系统结构熵理论,从产业在区际和区内聚集分布信息出发,融合行业路径和地区路径分析法于一体,提出并证明了可以用区位结构熵全面衡量产业在空间上的分布状况.在此基础上,构建一维区域分工指数,综合测定区域分工水平.最后,以我国工业空间分布为例,例证了该方法是合理的、可行的,具有一定的推广和应用价值.