Genetic algorithm for effective open port selection for a web filter

As cyber security is a major challenge in the widespread deployment of the latest technologies, the importance of selecting the open ports for a given web filter cannot be overemphasized. A network administrator would want to select a combination of ports that would be most beneficial to the users and these ports would be treated as least vulnerable. However, this is not a trivial task and can be very time-consuming, O(n!), if brute force or other naïve approaches are used to select a given number of ports from 65,536 ports available. As genetic algorithms (GAs) are commonly used to obtain near-optimal solution for complex and time-consuming tasks, this paper proposes a GA for the selection of open ports for a web filter. The gene value for each port is based on the malicious issues associated with the port and the importance of the port to the client using the web filter. The proposed algorithm is implemented in Java, and the simulation results show that GA is very accurate in identifying open ports for a given web filter.     

Improved algorithms for optimal length resolution refutation in difference constraint systems

This paper is concerned with the design and analysis of improved algorithms for determining the optimal length resolution refutation (OLRR) of a system of difference constraints over an integral domain. The problem of finding short explanations for unsatisfiable Difference Constraint Systems (DCS) finds applications in a number of design domains including program verification, proof theory, real-time scheduling, and operations research. These explanations have also been called “certificates” and “refutations” in the literature. This problem was first studied in Subramani (J Autom Reason 43(2):121–137, 2009), wherein the first polynomial time algorithm was proposed. In this paper, we propose two new strongly polynomial algorithms which improve on the existing time bound. Our first algorithm, which we call the edge progression approach, runs in O(n ² · k + m · n · k) time, while our second algorithm, which we call the edge relaxation approach, runs in O(m · n · k) time, where m is the number of constraints in the DCS, n is the number of program variables, and k denotes the length of the shortest refutation. We conducted an extensive empirical analysis of the three OLRR algorithms discussed in this paper. Our experiments indicate that in the case of sparse graphs, the new algorithms discussed in this paper are superior to the algorithm in Subramani (J Autom Reason 43(2):121–137, 2009). Likewise, in the case of dense graphs, the approach in Subramani (J Autom Reason 43(2):121–137, 2009) is superior to the algorithms described in this paper. One surprising observation is the superiority of the edge relaxation algorithm over the edge progression algorithm in all cases, although both algorithms have the same asymptotic time complexity.     

Double indices-induced FCM clustering and its integration with fuzzy subspace clustering

As one of the most popular algorithms for cluster analysis, fuzzy c-means (FCM) and its variants have been widely studied. In this paper, a novel generalized version called double indices-induced FCM (DI-FCM) is developed from another perspective. DI-FCM introduces a power exponent r into the constraints of the objective function such that the fuzziness index m is generalized and a new criterion of selecting an appropriate fuzziness index m is defined. Furthermore, it can be explained from the viewpoint of entropy concept that the power exponent r facilitates the introduction of entropy-based constraints into fuzzy clustering algorithms. As an attractive and judicious application, DI-FCM is integrated with a fuzzy subspace clustering (FSC) algorithm so that a new fuzzy subspace clustering algorithm called double indices-induced fuzzy subspace clustering (DI-FSC) algorithm is proposed for high-dimensional data. DI-FSC replaces the commonly used Euclidean distance with the feature-weighted distance, resulting in having two fuzzy matrices in the objective function. A convergence proof of DI-FSC is also established by applying Zangwill’s convergence theorem. Several experiments on both artificial data and real data were conducted and the experimental results show the effectiveness of the proposed algorithm.     

Techniques for Edge Stratification of Complex Graph Drawings

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.     

Routing with multiple quality-of-services constraints: An approximation perspective

Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality.     

Adaptive spatial information-theoretic clustering for image segmentation

The incorporation of spatial context into clustering algorithms for image segmentation has recently received a significant amount of attention. Many modified clustering algorithms have been proposed and proven to be effective for image segmentation. In this paper, we propose a different framework for incorporating spatial information with the aim of achieving robust and accurate segmentation in case of mixed noise without using experimentally set parameters based on the original robust information clustering (RIC) algorithm, called adaptive spatial information-theoretic clustering (ASIC) algorithm. The proposed objective function has a new dissimilarity measure, and the weighting factor for neighborhood effect is fully adaptive to the image content. It enhances the smoothness towards piecewise-homogeneous segmentation and reduces the edge blurring effect. Furthermore, a unique characteristic of the new information segmentation algorithm is that it has the capabilities to eliminate outliers at different stages of the ASIC algorithm. These result in improved segmentation result by identifying and relabeling the outliers in a relatively stronger noisy environment. Comprehensive experiments and a new information-theoretic proof are carried out to illustrate that our new algorithm can consistently improve the segmentation result while effectively handles the edge blurring effect. The experimental results with both synthetic and real images demonstrate that the proposed method is effective and robust to mixed noise and the algorithm outperforms other popular spatial clustering variants.     

Scheduling multicast traffic in input-buffered ATM switch

Performance of an input-buffered ATM switch is limited by the head-of-line (HOL) blocking problem. HOL blocking is even more pronounced in multicast switch where cells compete for multiple outputs simultaneously. Previous studies in input-buffered unicast switch have shown that HOL blocking can only be eliminated by using per-output queuing and sophisticated scheduling methods, such as the maximal weight matching (MWM) or the parallel iterative matching (PIM) methods. The MWM or PIM types of scheduling algorithm cannot be applied to multicast switch because of the high computation complexity. In this paper, we present a reservation based scheduling algorithm, which employs per-VC queuing for multicast connections and per-output queuing for unicast connections. Instead of the input ports sending a huge amount of state information to the output ports for processing, we circulate reservation vectors amongst the input ports. Each input port will then make reservation based on its local state and the availability of the output ports. The scheduling is done on a frame by frame basis. While the input ports are transmitting cells according to the schedule of the current frame, the next frame schedule is computed. Simulations reveal that our method substantially outperforms the methods that employ FIFO queuing discipline.     

Integrated design of workcells and unidirectional flowpath layout

In manufacturing cells layout design with a unidirectional flow system, the accurate distance between two workcells can be uncovered with both the determination of IO port locations after the layout design of the cell with its orientation and the unidirectional flowpath layout design. This paper presents the method to obtain a global solution for manufacturing workcells and unidirectional flowpath layout design (ICFLD) with consideration of IO ports of workcells. The flow distance between two workcells is calculated from output port of one workcell to input port of the other workcell through the unidirectional flowpath layout. A zero-one integer programming model is developed for the ICFLD problem. And a heuristic algorithm for the ICFLD problem is developed by decomposing the ICFLD problem into two subproblems and iteratively and alternately solving the decomposed subproblems. Computational experiments are performed and its results are analyzed.     

Optimal and efficient filtering algorithms for table constraints

Filtering algorithms for table constraints can be classified in two categories: constraint-based and value-based. In the constraint-based approaches, the propagation queue only contains information on the constraints that must be reconsidered. For the value-based approaches, the propagation queue also contains information on the removed values. This paper proposes five efficient value-based algorithms for table constraints. Two of them (AC5TCOpt-Tr and AC5TCOpt-Sparse) are proved to have an optimal time complexity of O(r·t+r·d) per table constraint. Substantial experimental results are presented. An empirical analysis is conducted on the effect of the arity of the tables. The experiments show that our propagators are the best when the arity of the table is 3 or 4. Indeed, on instances containing only binary constraints, our algorithms are outperformed by classical AC algorithm AC3rm. AC3rm is dedicated to binary constraints. However, all our algorithms outperform existing state-of-the-art constraint based STR2+ and MDD ^c and the optimal value-based STR3 algorithms on those instances. On instances with small arity tables (up to arity 4), all our algorithms are generally faster than STR2+, MDD ^c and than STR3. AC5TCOpt-Sparse is globally the best propagator on those benchmarks. On benchmarks containing large arity tables (arity 5 or more), each of the three existing state-of-the-art algorithms is the winning strategy on one different benchmark.     

基于全局端口状态感知的拥塞控制算法CAGPS

针对传统拥塞控制算法主要依据本地信息进行拥塞判断和丢弃决策的缺陷，本文提出了基于全局端口状态感知的拥塞控制算法CAGPS，更全面地考虑远程转发引擎的拥塞状态信息和远程转发引擎各端口的拥塞信息，以期获得更加合理的流控决策，从而提高路由器的整体吞吐率。本文最后描述了CAGPS在基于网络处理器的核心路由器上的实现方法。     

An exact algorithm with learning for the graph coloring problem

Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5.     

A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.     

Cooperative control through objective achievement

Cooperative control is a key issue for multirobot systems in many practical applications. In this paper, we address the problem of coordinating a set of mobile robots in the RoboCup soccer middle-size league. We show how the coordination problem that we face can be cast as a specific coalition formation problem, and we propose a distributed algorithm to efficiently solve it. Our approach is based on the distributed computation of a measure of satisfaction (called Agent Satisfaction) that each agent computes for each task. We detail how each agent computes the Agent Satisfaction by acquiring sensor perceptions through an omnidirectional vision system, extracting aggregated information from the acquired perception, and integrating such information with that communicated by the teammates. We empirically validate our approach in a simulated scenario and within RoboCup competitions. The experiments in the simulated scenario allow us to analyse the behaviour of the algorithm in different situations, while the use of the algorithm in real competitions validates the applicability of our approach to robotic platforms involved in a dynamic and complex scenario.     

Random lattices,threshold phenomena and efficient reduction algorithms

Two new lattice reduction algorithms are presented and analyzed. These algorithms, called the Schmidt reduction and the Gram reduction, are obtained by relaxing some of the constraints of the classical LLL algorithm. By analyzing the worst case behavior and the average case behavior in a tractable model, we prove that the new algorithms still produce “good” reduced basis while requiring fewer iterations on average. In addition, we provide empirical tests on random lattices coming from applications, that confirm our theoretical results about the relative behavior of the different reduction algorithms.     

The Traveling Salesman Problem with Draft Limits

In maritime transportation, routing decisions are sometimes affected by draft limits in ports. The draft of a ship is the distance between the waterline and the bottom of the ship and is a function of the load onboard. Draft limits in ports can thus prevent ships to enter these ports fully loaded and may impose a constraint on the sequence of visits made by a ship. This paper introduces the Traveling Salesman Problem with Draft Limits (TSPDL), which is to determine an optimal sequence of port visits under draft limit constraints. We present two mathematical formulations for the TSPDL, and suggest valid inequalities and strengthened bounds. We also introduce a set of instances based on TSPLIB. A branch-and-cut algorithm is applied on both formulations for all these instances. Computational results show that introducing draft limits make the problem much harder to solve. They also indicate that the proposed valid inequalities and strengthened bounds significantly reduce both the number of branch-and-bound nodes and the solution times.     

Search for all d-Mincuts of a limited-flow network

In this presentation, we developed an intuitive algorithm based on some simple concepts that were found in this study. It is more efficient than the best-known existing algorithm. The computational complexity of the proposed algorithm is analyzed and compared with the existing methods. One example is illustrated to show how all d-MCs are generated by our proposed algorithm. As evidence of the utility of the proposed approach, extensive computational results on random test problems are presented. Our results compare favorably with previously developed algorithms in the literature.Scope and purposeMany real-world systems are multistate systems composed of multistate components in which the reliability can be computed in terms of the lower bound points of level d, called d-Mincuts (d-MCs). Such systems (electric power, transportation, etc.) may be regarded as flow networks whose arcs have independent, discrete, limited and multivalued random capacities. In this study, all MCs are assumed to be known in advance and we focused on how to find the entire d-MCs before calculating the reliability value of a network. Analysis of our algorithm and comparison to existing algorithms shows that our proposed method has the following advantages: (1) the number of d-MC candidates is less than those in the existing methods, (2) the d-MC candidates are simpler to find and verify, which makes the method more effective than the existing methods, and (3) our method is easier to understand and implement.     

Optimized QoS-aware replica placement heuristics and applications in astronomy data grid

This paper studies the Quality-of-Service (QoS)-aware replica placement problem in a general graph model. Since the problem was proved NP-hard, heuristic algorithms are the current solutions to the problem. However, these algorithms cannot always find the effective replica placement strategy. We propose two algorithms that can obtain better results within the given time period. The first algorithm is called Cover Distance algorithm, which is based on the Greedy Cover algorithm. The second algorithm is an optimized genetic algorithm, in which we use random heuristic algorithms to generate initial population to avoid enormous useless searching. Then, the 0-Greedy-Delete algorithm is used to optimize the genetic algorithm solutions. According to the performance evaluation, our Cover Distance algorithm can obtain relatively better solution in time critical scenarios. Whereas, the optimized genetic algorithm is better when the replica cost is of higher priority than algorithm execution time. The QoS-aware data replication heuristic algorithms are applied into the data distribution service of an astronomy data grid pipeline prototype, and the operation process is studied in detail.     

Exact and approximate solutions of the container ship stowage problem

This paper deals with a stowage plan for containers in a container ship. Containers on board a container ship are placed in stacks, located in many bays. Since the access to the containers is only from the top of the stack, a common situation is that contianers designated for port J must be unloaded and reloaded at port I (before J) in order to access containers below them, designated for port I. This operation is called “shifting”. A container ship calling many ports, may encounter a large number of shifting operations, some of which can be avoided by efficient stowage planning. In general, the stowage plan must also take into account stability and strength requirements, as well as several other constraints on the placement of containers. In this paper we deal with stowage planning in order to minimize the number of shiftings, without considering stability constraints. First, a 0–1 binary linear programming formulating is presented that can find the optimal solution for stowage in a single rectangular bay of a vessel calling a given number of ports, assuming that the number of constainers to ship is known in advance. This model was successfully implemented using the GAMS software system. It was found, however, that finding the optimal solution using this model is quite limited, because of the large number of binary variables needed for the formulation. For this reason, several alternative heuristic algorithms were developed. The one presented here is based on a “reduced” transportation matrix. Containers with the same source and destination ports are stowed in full stacks as much as possible, and only the remaining containers are allocated by the binary linear programming model. This approach often allows the stowage planning of a much larger number of containers than using the exact formulation.     

An efficient server bandwidth costs decreased mechanism towards mobile devices in cloud-assisted P2P-VoD system

Recently, more and more devices with small buffer size such as PDAs or mobile phones are joining in the VoD system, which leads to two major challenges: how to efficiently distribute their bandwidth resources with small buffer size, and how to provide assistant mechanism to make them playback smoothness. In face of this situation and for the purpose of decreasing the server bandwidth costs, we propose a peers’ downloading mechanism called NCDLT to solve above challenges. It contains two algorithms. The first is neighbors and chunks downloading selection (NCS) algorithm and it ensures peers to find neighbors who can provide video data with lower refusal rate. The second is distributed linear taxation algorithm (DLT) and it makes peers with lower capability acquire enough download rate to reduce the request to servers. The simulation results demonstrate that our algorithms can offload the server bandwidth costs and improve the download rate of peers with small buffer size.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems