The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the ℓp norm (CVP_p) over rank n lattices cannot be solved in 2^(1-≥) n time for any constant ≥ 0 unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to almost all values of p ≥ 1, not including the even integers. This comes...
In Bike-Sharing System (BSS), great efforts have been devoted to performing resources prediction, redistribution and trip planning to alleviate the unbalance of resources and inconvenience of bike utilization caused by the explosion of users. However, there is few work in trip planning noticing that the complete trip composes of three segments: from user's start point to a start station, from the...
In the communication problem UR (universal relation), Alice and Bob respectively receive x, y ∊{0,1\}^n with the promise that x≠ y. The last player to receive a message must output an index i such that x_i≠ y_i. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly \Theta(\min\{n,\log(1/δ)\log^2(\frac...
In consistent flow migration, the task is to change the paths the flows take in the network, but without inducing congestion during the update process. Even though the rise of Software Defined Networks allows for centralized control of path changes, the execution is still performed in an inherently asynchronous system, the switches distributed over the network. To this end, a multitude of scheduling...
March W-1T1R, a high fault coverage March test, is proposed to cover not only the tranditional fault set, but also the newly discovered write disturbance fault (WDF) and dynamic write disturbance fault (dWDF) in 1T1R memristor arrays. The analysis shows that the March W-1T1R algorithm with complexity of 17N, where N is the number of memory cells in the array, enhances the fault coverage only with...
A disease propagating in a community or a rumor spreading in a social network can be described by a contact network whose nodes are persons or centers of contagion and links heterogeneous relations among them. Suppose that a disease or a rumor originating from a single source among a set of suspects spreads in a network, how to locate this disease/rumor source? This problem is crucial and challenging...
Negative sequential patterns (NSP) become increasingly important and most of the existing methods introduce so strict constraints that many meaningful patterns would be lost. In this paper, we loosen these constraints and solve a series of consequent problems. Firstly, negative containment is defined to determine whether a data sequence contains a negative sequence. Secondly, an efficient method to...
In the area of applied optimisation, heuristics are a popular means to address computational problems of high complexity. Modelling the problem and mapping all variations of its solution into a so-called solution space are integral parts of this process. Representing solutions as graphs is common and, for a special type of graph, Prüfer Code (PC) offers a computationally efficient mapping (algorithms...
Grouping the vertex of the graph into sets of certain sizes such that minimum number of edges cross between the sets is called graph partitioning. This NP (Non-deterministic Polynomial time)-complete problem has important applications in computing, task scheduling, and parallel processing. We are implementing Kernighan-Lin, a local algorithm on both a Central Processing Unit (CPU) and a Graphics Processing...
In context of human-machine-interaction trajectories need to be rerouted or re-planned with reduced dynamical constraints in order to avoid collisions. This requires online feasible algorithm for trajectory planning in space. In this paper a new method for planning time-optimal trajectories subject to dynamic and geometrical constraints is proposed. Distinctively to other work, both spatial and temporal...
The Information-Centric Network (ICN) is very promising in the area of Complex Active Networks (CANs), where the data-centric approach is useful in reducing the data retrieval latency as well as the network traffic of active networking services. Also, the in-network caching and processing capabilities in ICN limits the massive data access to the data producers and so relaxes the need of continuous...
We address a combinatorial optimization problem, namely the 1D array partitioning problem (1D-APP), having several real world applications such as scheduling independent tasks in parallel environments under contiguity constraint. We propose an exact binary search algorithm of pseudo-linearithmic complexity since the latter depends on the input data values. Our approach involves two phases. The first...
We are interested in an easy combinatorial optimization problem having several applications in the real world, namely the matrix chain product problem that may be solved by a well known dynamic programming algorithm (DPA). Our contribution is two-fold. It first consists in the design of an approach based on the DPA for the determination of multiple optimal solutions i.e. optimal parenthesizations...
We address the 1D array partitioning problem (1D- APP), an easy combinatorial optimization problem, for which an exact dynamic programming algorithm (DPA) is known in the literature. The DPA is structured in a perfect three DO-loop nest (3DLN) with affine loop bounds. Due to its cubic complexity which may be too time consuming for large size real world problems, we propose a parallelization approach...
Future 5G network provides network slices for applications of different areas on the same physical network. Low-latency is the most key indicators of demand for the slices. How to establish the low-latency network slices is an essential question. This article proposes a mapping algorithm for low-latency network slices based on linear programming. Firstly, this problem can be defined as a linear programming...
This paper proposes a modified IMWBF decoding algorithm for low-density parity-check (LDPC) codes. In the proposed modification, the magnitude of the received signal is updated when the number of the unsatisfied parity-check equations participated by this received signal is larger than a predetermined threshold. Through this modification, the outlier, defined as the undesired large-magnitude received...
Two main techniques have been used so far to solve the #P-hard problem #SAT. The first one, used in practice, is based on an extension of DPLL for model counting called exhaustive DPLL. The second approach, more theoretical, exploits the structure of the input to compute the number of satisfying assignments by usually using a dynamic programming scheme on a decomposition of the formula. In this paper,...
The importance of using heuristics in an optimization algorithm is well established, particularly in solving complex real-world problems. It is then expected that users know certain key problem information a priori and are able to implement the information in a suitable optimization algorithm. However, in many problems, such problem information may not be available before an optimization task is performed,...
Load balancing is a key aspect to face when implementing any parallel application for Graphic Processing Units (GPUs). It is particularly crucial if one considers that it strongly impacts on performance, power and energy efficiency of the whole application. Many different partitioning techniques have been proposed in the past to deal with either very regular workloads (static techniques) or with irregular...
In all the researches in wireless sensor networks, cameras are increasingly utilized for their surveillance capabilities. In this paper, we elaborately discuss about the problem of Full-View Barrier Coverage with Rotatable Camera Sensors (FBR), including weakly and strongly connected versions. FBR is proven to be NP-hard in this paper by reducing Group Steiner Tree problem to it. Our goal is to reduce...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.