An Exact Virtual Network Embedding Algorithm Based on Integer Linear Programming for Virtual Network Request with Location Constraint

Network virtualization is known as a promising technology to tackle the ossification of current Internet and will play an important role in the future network area. Virtual network embedding(VNE) is a key issue in network virtualization. VNE is NP-hard and former VNE algorithms are mostly heuristic in the literature.VNE exact algorithms have been developed in recent years. However, the constraints of exact VNE are only node capacity and link bandwidth.Based on these, this paper presents an exact VNE algorithm, ILP-LC, which is based on Integer Linear Programming(ILP), for embedding virtual network request with location constraints. This novel algorithm is aiming at mapping virtual network request(VNR) successfully as many as possible and consuming less substrate resources.The topology of each VNR is randomly generated by Waxman model. Simulation results show that the proposed ILP-LC algorithm outperforms the typical heuristic algorithms in terms of the VNR acceptance ratio, at least 15%.

Causal constraint pruning for exact learning of Bayesian network structure

How to improve the efficiency of exact learning of the Bayesian network structure is a challenging issue.In this paper,four different causal constraints algorithms are added into score calculations to prune possible parent sets,improving state-ofthe-art learning algorithms’efficiency.Experimental results indicate that exact learning algorithms can significantly improve the efficiency with only a slight loss of accuracy.Under causal constraints,these exact learning algorithms can prune about 70%possible parent sets and reduce about 60%running time while only losing no more than 2%accuracy on average.Additionally,with sufficient samples,exact learning algorithms with causal constraints can also obtain the optimal network.In general,adding max-min parents and children constraints has better results in terms of efficiency and accuracy among these four causal constraints algorithms.

Parallel Quick Search Algorithm for the Exact String Matching Problem Using OpenMP

String matching is seen as one of the essential problems in computer science. A variety of computer applications provide the string matching service for their end users. The remarkable boost in the number of data that is created and kept by modern computational devices influences researchers to obtain even more powerful methods for coping with this problem. In this research, the Quick Search string matching algorithm are adopted to be implemented under the multi-core environment using OpenMP directive which can be employed to reduce the overall execution time of the program. English text, Proteins and DNA data types are utilized to examine the effect of parallelization and implementation of Quick Search string matching algorithm on multi-core based environment. Experimental outcomes reveal that the overall performance of the mentioned string matching algorithm has been improved, and the improvement in the execution time which has been obtained is considerable enough to recommend the multi-core environment as the suitable platform for parallelizing the Quick Search string matching algorithm.

Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O（L）. Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path.

EVOLUTION FILTRATION PROBLEMS WITH SEAWATER INTRUSION: TWO-PHASE FLOW DUAL MIXED VARIATIONAL ANALYSIS

Tow-phase flow mixed variational formulations of evolution filtration problems with seawater intrusion are analyzed. A dual mixed fractional flow velocity-pressure model is considered with an air-fresh water and a fresh water-seawater characterization. For analysis and computational purposes, spatial decompositions based on nonoverlapping multidomains, above and below the sea level, are variationally introduced with internal boundary fluxes dualized as weak transmission constraints. Further, parallel augmented and exactly penalized duality algorithms, and proximation semi-implicit time marching schemes, are established and analyzed.

Study of Array Antenna Pattern Synthesis Based on Sparse Sensing

Aiming at the problem that a large number of array elements are needed for uniform arrays to meet the requirements of direction map,a sparse array pattern synthesis method is proposed in this paper based on the sparse sensing theory.First,the Orthogonal Matching Pursuit(OMP)algorithm and the Exact Augmented Lagrange Multiplier(EALM)algorithm were improved in the sparse sensing theory to obtain a more efficient Orthogonal Multi⁃Matching Pursuit(OMMP)algorithm and the Semi⁃Exact Augmented Lagrange Multiplier(SEALM)algorithm.Then,the two improved algorithms were applied to linear array and planar array pattern syntheses respectively.Results showed that the improved algorithms could achieve the required pattern with very few elements.Numerical simulations verified the effectiveness and superiority of the two synthetic methods.In addition,compared with the existing sparse array synthesis method,the proposed method was more robust and accurate,and could maintain the advantage of easy implementation.

Distributed exact Grover’s algorithm

Distributed quantum computation has gained extensive attention.In this paper,we consider a search problem that includes only one target item in the unordered database.After that,we propose a distributed exact Grover’s algorithm(DEGA),which decomposes the original search problem into■n/2■parts.Specifically,(i)our algorithm is as exact as the modified version of Grover’s algorithm by Long,which means the theoretical probability of finding the objective state is 100%;(ii)the actual depth of our circuit is 8(n mod 2)+9,which is less than the circuit depths of the original and modified Grover’s algorithms,1+8■π/4√2^(n)■and 9+8■π/4√2^(n)-1/2■,respectively.It only depends on the parity of n,and it is not deepened as n increases;(iii)we provide particular situations of the DEGA on MindQuantum(a quantum software)to demonstrate the practicality and validity of our method.Since our circuit is shallower,it will be more resistant to the depolarization channel noise.

A review on the electric vehicle routing problems: Variants and algorithms

Over the past decade,electric vehicles(EVs)have been considered in a growing number of models and methods for vehicle routing problems(VRPs).This study presents a comprehensive survey of EV routing problems and their many variants.We only consider the problems in which each vehicle may visit multiple vertices and be recharged during the trip.The related literature can be roughly divided into nine classes:Electric traveling salesman problem,green VRP,electric VRP,mixed electric VRP,electric location routing problem,hybrid electric VRP,electric dial-a-ride problem,electric two-echelon VRP,and electric pickup and delivery problem.For each of these nine classes,we focus on reviewing the settings of problem variants and the algorithms used to obtain their solutions.

Definition and Algorithms for Reliable Steiner Tree Problem

This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)problem.The authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for it.The definition is based on the reliability of full components instead of Steiner vertices.The task is thus to find the most reliable full components to make up an optimum reliable Steiner tree.The exact algorithm designed for this problem utilizes a dynamic programming frame.The approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.

Parameterized Algorithmics for Computational Social Choice:Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.

Minimizing makespan of a production batch within concurrent systems:Seru production perspective

This paper discusses the makespan minimization of a production batch within a specific concurrent system,seru production system.A seru production system consists of multiple independent serus.A seru is a compact assembly origination in which products are assembled from-the-beginning-to-the-end without disruptions.One capability of a seru production system is its responsiveness.A performance measure used to evaluate a seru system’s responsiveness is the makespan of production batches assembled within the seru system.This study addresses the makespan minimization problem through an optimal seru loading policy.The problem is formulated as a min-max integer optimization model.An exact dimension-reduction Algorithm is developed to obtain the optimal allocation that minimizes the makespan.We show that the solution space increases very quickly.In contrast,our algorithm is efficient with a polynomial computational complexity of,where is the total number of serus in a seru system.To verify the usefulness of the developed exact dimension-reduction algorithm,we compare it with a widely practiced greedy algorithm through experiments.We find that our optimal algorithm is robust in most cases and the greedy algorithm is efficient when variability in production efficiencies is high.This result can guide us to adopt different algorithms in different business environments.If the variability in production efficiencies is high,e.g.,new employees and/or new products assembly,the greedy algorithm is efficient.For other cases,our optimal algorithm should be adopted to obtain the minimum makespan.We also extend the method to the application of a rotating seru.

A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing

Emerging applications widely use field-programmable gate array(FPGA)prototypes as a tool to verify modern very-large-scale integration(VLSI)circuits,imposing many problems,including routing failure caused by the limited number of connections among blocks of FPGAs therein.Such a shortage of connections can be alleviated through time-division multiplexing(TDM),by which multiple signals sharing an identical routing channel can be transmitted.In this context,the routing quality dominantly decides the performance of such systems,proposing the requirement of minimizing the signal delay between FPGA pairs.This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support,aiming to minimize the maximum TDM ratio.The algorithm consists of two major stages:(1)A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees.(2)A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints.Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works,and the results manifest that our method achieves a better TDM ratio in comparison.

Computing Halfspace Depth Contours Based on the Idea of a Circular Sequence

This paper presents a new effcient algorithm for exactly computing the halfspace depth contours based on the idea of a circular sequence. Unlike the existing methods, the proposed algorithm segments the unit sphere directly relying on the permutations that correspond to the projections of observations onto some unit directions, without having to use the technique of parametric programming.Some data examples are also provided to illustrate the performance of the proposed algorithm.