Hose workload based exact algorithm for the optimal design of virtual private networks

The Virtual Private Networks (VPN) optimal bandwidth allocation problem with tree topology has been widely discussed in the literature. Most of the algorithms proposed by researchers to solve this problem use approximation schemes. In this paper, we propose an exact and efficient Branch-and-Cut algorithm for the problem in the context of a hose workload model. In particular, we consider the case when the ingress and egress traffic at VPN endpoints are asymmetric and the links of the network have unbounded capacities. The algorithm proposed here is based on a linear integer programming formulation for the problem introduced by Kumar et al. (2002) [2]. Using this and a deep investigation of the polyhedral structure of that formulation, our algorithm permits to solve large instances of the problem having up to 120 nodes and 10 terminals.     

用于二维不规则排样的离散临界多边形模型

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.     

A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.     

Fast and accurate mining of correlated heavy hitters

The problem of mining correlated heavy hitters (CHH) from a two-dimensional data stream has been introduced recently, and a deterministic algorithm based on the use of the Misra–Gries algorithm has been proposed by Lahiri et al. to solve it. In this paper we present a new counter-based algorithm for tracking CHHs, formally prove its error bounds and correctness and show, through extensive experimental results, that our algorithm outperforms the Misra–Gries based algorithm with regard to accuracy and speed whilst requiring asymptotically much less space.     

An ID-based digital watermarking protocol for copyright protection

Digital watermarking techniques are a means of protecting the copyrights of digital contents. In this paper, we propose an identity-based (ID-based) digital watermarking protocol and point out several previously unpublished flaws in Hwang et al. (2005)’s scheme. We hope that by identifying the design flaws, similar structural mistakes can be avoided in future designs. We also claim that our proposed digital watermarking scheme can effectively solve the problem of multiple claims of ownership, and is suitable for any practical and secure watermarking algorithm.     

A parallel two-list algorithm for the knapsack problem

An n-element knapsack problem has 2ⁿ possible solutions to search over, so a task which can be accomplished in 2″ trials if an exhaustive search is used. Due to the exponential time in solving the knapsack problem, the problem is considered to be very hard. In the past decade, much effort has been done in order to find techniques which could lead to practical algorithms with reasonable running time. In 1994, Chang et al. proposed a brilliant parallel algorithm, which needs O(2^n/8) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Chang et al.'s parallel algorithm is O(2^5n/8). In this paper, we propose a parallel algorithm to improve Chang et al.'s parallel algorithm by reducing the time complexity to be O(2^3n/8) under the same O(2^n/8) processors available. Thus, the proposed parallel algorithm has a cost of O(2^n/2). It is an improvement over previous literature. We believe that the proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.     

单调重叠联盟下的最优联盟结构生成

针对重叠联盟的合作博弈框架（OCF games）中重叠联盟结构生成（OCSG）求解困难的问题,提出了一种基于贪心方法的有效算法。首先使用了一种带有联盟数量k约束的OCF博弈（kOCF games）模型来限制OCSG问题的规模;然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度,并基于相似度量定义了单调性的性质,这意味着某一联盟结构与最优联盟结构的相似度越高,该联盟的单调性的值就越大;最后对于具有单调性质的kOCF博弈,采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心（CCG）算法来求解给定的OCSG问题,并在理论上证明了CCG算法的复杂度是O（n2^k+1）。通过实验分析和验证了不同参数和联盟值分布对所提算法性能的影响,并把该算法与Zick等提出的算法（ZICK Y,CHALKIADAKIS G,ELKIND E,et al. Cooperative games with overlapping coalitions： charting the tractability frontier. Artificial Intelligence,2019,271：74-97）在约束条件等方面进行了对比,得出了当联盟最大数量k被常数约束时所提算法的搜索次数随agent的个数基本呈线性增长的结果。可见CCG算法是固定参数k可解的,而且拥有更好的适用性。     

Distributed Object Location in a Dynamic Network

Modern networking applications replicate data and services widely, leading to a need for location-independent routing—the ability to route queries to objects using names independent of the objects’ physical locations. Two important properties of such a routing infrastructure are routing locality and rapid adaptation to arriving and departing nodes.We showhowthese two properties can be efficiently achieved for certain network topologies. To do this, we present a new distributed algorithm that can solve the nearest-neighbor problem for these networks. We describe our solution in the context of Tapestry, an overlay network infrastructure that employs techniques proposed by Plaxton et al. [24].     

改进临界多边形生成算法

在Burke等人提出的用于求解临界多边形的移动碰撞算法基础之上,提出了一种更加高效的求取NFP的改进算法。该算法大大降低了问题的几何复杂性,简化了计算最小移动距离的方法,使许多启发式策略可以更加容易地与该算法结合来求解二维排样问题。实例验证了改进算法是有效且可行的,已应用于皮革自动排样软件中。     

一类多项式光滑函数的逼近精度

针对一类支持向量机的多项式光滑函数,采用二分法求解它们尚未解决的逼近精度问题。为克服二分法可能会漏根的缺点,首先把多项式光滑函数的逼近精度问题表示为一个求逼近函数的最大值问题,把这个逼近函数分成4 段,分别求出每段的最大值,然后得到逼近函数在整个x轴上的最大值。并以1阶和2阶多项式光滑函数为例,用二分法解决了它们的逼近精度问题。研究表明,二分法是求解这类多项式光滑函数逼近精度的有效方法。     

A novel ID-based group signature

Group signatures, first introduced by Chaum and Heyst at Eurocrypt'91, allow individual members of a group to make signatures on behalf of the group while providing the signer's anonymity. Most of the previously proposed group signature schemes are based on the discrete logarithm problem, the public keys of users are not identity information, except for the ID-based scheme proposed by Park et al. in 1997. However, Park et al.'s scheme has a serious problem, which is that all of the previous group signatures signed by other members will be no longer valid if the group is changed. Moreover, the length of the group signature grows linearly with the number of group members, which makes their proposed scheme inefficient. In this paper, the authors propose a novel ID-based group signature scheme which can solve the problem raised by the inclusion of a new group member or the exclusion of an old group member. Meanwhile, compared to Park et al.'s scheme, our scheme requires less computing time for generating the group signature and verifying the group signature. The security of the proposed ID-based group signature scheme is based on the difficulty of computing the discrete logarithm modulo for a composite number.     

Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approach

Hybrid flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. Multiprocessor task scheduling problem can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. Hybrid Flow Shop Scheduling with Multiprocessor Task (HFSMT) problem is known to be NP-hard. In this study we present an effective parallel greedy algorithm to solve HFSMT problem. Parallel greedy algorithm (PGA) is applied by two phases iteratively, called destruction and construction. Four constructive heuristic methods are proposed to solve HFSMT problems. A preliminary test is performed to set the best values of control parameters, namely population size, subgroups number, and iteration number. The best values of control parameters and operators are determined by a full factorial experimental design using our PGA program. Computational results are compared with the earlier works of O?uz et al. [1], [3], and O?uz [2]. The results indicate that the proposed parallel greedy algorithm approach is very effective in terms of reduced total completion time or makespan (C_max) for the attempted problems.     

A DNA-based data hiding technique with low modification rates

In 2010, Shiu et al. proposed three DNA-based reversible data hiding schemes with high embedding capacity. However, their schemes were not focused on DNA modification rate or the expansion problem. Therefore, we propose a novel reversible data hiding scheme based on histogram technique to solve the weaknesses of Shiu et al.’s schemes. The proposed scheme transforms the DNA sequence into a binary string and then combines several bits into a decimal integer. These decimal integers are used to generate a histogram. Afterwards, the proposed scheme uses a histogram technique to embed secret data. The experimental results show that the modification rate of our proposed scheme is 69 % lower than that of Shiu et al.’s schemes for the same embedding capacity. In addition, the length of the DNA sequence remains unchanged in the proposed scheme.     

On the security enhancement for anonymous secure e-voting over computer network

Mu and Varadharajan proposed an electronic voting system which can be utilized in large-scale elections in 1998. Recently, Lin et al. showed that Mu and Varadharajan's scheme has a weakness. That is, voters can successfully vote more than once without being detected. To avoid this weakness, Lin et al. proposed a modified scheme. However, this paper shows that the Lin et al.'s modification allows the Authentication Server to identify the voters of published tickets so that voters will lose their privacy. An improved scheme is further proposed to solve this problem and thus enhance the security.     

基于遗传策略的图像灰度多阈值选择方法

阈值法是图像处理中阈值选择的最重要方法之一,吸引了很多研究者的注意力。ChunDN等人将遗传算法引入到阈值选择问题中,提出了基于遗传算法的鲁棒图像分割准则。文中对遗传算法做了改进,提出了自己的图像分割方法,并针对多阈值选择中计算量太大的问题,提出了自己的算法。通过实验将该算法与模拟退火算法进行了比较,结果充分显示了算法的有效性。     

Solving Systems of Difference Constraints Incrementally with Bidirectional Search

We propose an incremental algorithm for the problem of maintaining systems of difference constraints. As a difference from the unidirectional approach of Ramalingam et al., it employs bidirectional search, which is similar to that of Alpern et al., and has a bounded runtime complexity in the worst case in terms of the size of changes. The major challenge is how to update the solution efficiently after the bidirectional search discovers a region that needs changes. Experimental results show that our approach is much faster in runtime and generates much smaller changes than the algorithm in Ramalingam et al. We also perform an experimental study on the edge value heuristic Alpern et al. and results show that a simpler method may be faster in practice.     

Coverage and Exposure Paths in Wireless Sensor Networks

Wireless sensor networks have posed a number of challenging problems such as localization, deployment and tracking, etc. One of the interesting problems is the calculation of the coverage and exposure paths for the sensor networks. This paper presents a fully localized algorithm to solve the worst coverage problem first introduced by Meguerdichian et al. The nodes of the sensor network cooperate to construct the worst coverage path only by the one-hop neighbor＇s information, thus avoiding the massive communication and conserving the energy. The correctness of the proposed algorithm is proved formally under the sensing diminishing model. Moreover, this algorithm can be easily extended to solve the minimal exposure problem with local information as well.     

The economic lot scheduling problem in limited-buffer flexible flow shops: Mathematical models and a discrete fruit fly algorithm

This paper considers the lot scheduling problem in the flexible flow shop with limited intermediate buffers to minimize total cost which includes the inventory holding and setup costs. The single available mathematical model by Akrami et al. (2006) for this problem suffers from not only being non-linear but also high size-complexity. In this paper, two new mixed integer linear programming models are developed for the problem. Moreover, a fruit fly optimization algorithm is developed to effectively solve the large problems. For model’s evaluation, this paper experimentally compares the proposed models with the available model. Moreover, the proposed algorithm is also evaluated by comparing with two well-known algorithms (tabu search and genetic algorithm) in the literature and adaption of three recent algorithms for the flexible flow shop problem. All the results and analyses show the high performance of the proposed mathematical models as well as fruit fly optimization algorithm.     

An efficient deterministic heuristic for two-dimensional rectangular packing

This paper proposes a deterministic heuristic, a best fit algorithm (BFA), for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. There are two stages in this new approach: the constructive stage and the tree search stage. The former aims to rapidly generate an initial solution by employing the concepts of action space and fit degree in evaluating different placements. The latter seeks to further improve the solution and searches for promising placements by a partial tree search procedure. We then compare BFA with other approaches in terms of solution quality and computing time. We carry out computational experiments on two sets of well-known benchmark instances, C21 proposed by Hopper and Turton, and N13 proposed by Burke et al. BFA gained an average filling rate of 100% for the C21 instances within short times, indicating that all the layouts obtained are optimal. To the best of our knowledge, this is the first time that optimal layouts on all the 21 instances were obtained by a deterministic algorithm. As for the N13 instances, to date, researchers have found optimal solutions to the first three instances, whereas BFA solved seven, including the first three, within a reasonable period. An additional work is to adapt BFA to solve a relevant problem, the constrained two-dimensional cutting (or packing) problem (CTDC). Though BFA is not for the CTDC in the original design such that some specific characteristics of CTDC are not considered, the adapted algorithm still performed well on 21 public CTDC instances.     

邻域小波系数自适应的图像降噪

如何去除自然图像中的高斯白噪声是图像处理中的一个经典问题。基于小波收缩的NeighShrink降噪方法取得了很好的降噪效果,但是NeighShrink在所有小波子带上均使用了次优的universal阈值以及固定的邻域窗口尺寸,导致了较大的偏差,而且使得算法不健壮。为此,运用Stein的无偏风险估计改进了NeighShrink方法。该方法能够为每个小波子带确定最优的阈值和邻域窗口尺寸。实验结果显示,该方法取得了比NeighShrink更低的均方误差,也优于当前尖端的图像降噪算法—FeatShrink,其平均MSE大约低6%。