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.
In this paper, we present efficient geometric algorithms for the discrete constrained 1-D K-means clustering problem and extend our solutions to the continuous version of the problem. One key clustering constraint we consider is that the maximum difference in each cluster cannot be larger than a given threshold. These constrained 1-D K-means clustering problems appear in various applications, especially...
The performance of a DNA microarray is dependent on the quality of the probes it uses. A good probe is uniquely associated with a particular sequence that distinguishes it from other sequences. Most existing algorithms to solve the probe selection problem use the common approach that directly filters out “bad” probes or selects “good” probes of each gene. However, this approach requires a very long...
We present two absolute error approximation algorithms for a point-to-surface registration problem in 3D with applications in medical navigation systems. For a given triangulated or otherwise dense sampled surface , a small point set P ⊂ ℝ3 and an error bound μ we present two algorithms for computing the set of rigid motions, so that the directed Hausdorff distance...
A digital signature is a term used to describe a data string which associates a digital message with an assigned person only. Therefore, the main goal (or contribution) of this work is to study a simple method for generating digital signatures and cryptography communication using biometrics. The digital signature should be generated in the way that it can be verified by the existing cryptographic...
The best known algorithm computes the sensitivity of a given spaced seed on a random region with running time O((M + L)|B|), where M is the length of the seed, L is the length of the random region, and |B| is the size of seed-compatible-suffix set, which is exponential to the number of 0’s in the seed. We developed two algorithms to improve this running time: the first one improves the running time...
The confidential access to medical images becomes significant in recent years. In this paper, we propose two types of region-based selective encryption schemes to achieve secure access for medical images. The first scheme randomly flips a subset of the bits belonging to the coefficients in a Region of Interest inside of several wavelet sub-bands, which is performed in compression domain but only incurs...
Nowadays, it is still the primary problem to find the inhibitors of retrovirus, protease and integrase in anti-AIDS drug design. However, the research and experimental results about anti-AIDS inhibitors mainly exist in large numbers of scientific literature, not in readable format for computer. In this paper, we introduce an Ontology-based Information Extraction (OIE) approach to extract anti-AIDS...
Recently, hiding secret data in DNA becomes an important and interesting research topic. Some researchers hid data in non-transcribed DNA, non-translated RNA regions, or active coding segments. Unfortunately, these schemes either alter the functionalities or modify the original DNA sequences. As a result, how to embed the secret data into the DNA sequence without altering the functionalities and to...
In this paper, we resolve two open questions on the computation and approximation of an Arrow-Debreu equilibrium in a Leontief exchange economy: We prove that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, unless PPAD ⊆ P. We show that the smoothed complexity of any algorithm for computing a market equilibrium in a Leontief...
Our research is motivated by finding auction protocols to elegantly coordinate the sellers and buyers when there are multiple auctions. In our model, there are multiple sellers selling different items that are substitute to each other, multiple buyers each demanding exactly one item, and a market that is monopolistic competitive. We implement our auction coordination protocol by polynomial running...
This paper proposes a generalized on-line risk-reward model, by introducing the notion of the probabilistic forecast. Using this model, we investigate the on-line rental problem. We design the risk rental algorithms under the basic probability forecast and the geometric distribution probability forecast, respectively. In contrast to the existing competitive analyses of the on-line rental problem,...
This paper describes the experiments and results obtained from distributing an improved insertion heuristic for the scheduling of passengers’ trip requests over a fleet of vehicles. The distribution has been obtained by means of an agent architecture implemented over Jade. Agents make use of the contract-net protocol as base coordination mechanism for the planning and scheduling of passenger trips...
In this paper, we consider a map labeling problem to maximize the number of independent labels in the plane. We first investigate the point labeling model that each label can be placed on a given set of anchors on a horizontal line. It is known that most of the map labeling decision models on a single line (horizontal or slope line) can be easily solved. However, the label number maximization models...
We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of a LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of monotone Boolean function is equivalent to determining...
We study approximation streaming algorithms for the k-center problem in the fixed dimensional Euclidean space. Given an integer k ≥ 1 and a set S of n points in the d-dimensional Euclidean space, the k-center problem is to cover those points in S with k congruent balls with the smallest possible radius. For any ε> 0, we devise an $O({k\over \epsilon^d})$ -space (1 + ε)-approximation streaming...
We consider the problem of scheduling n jobs with release times on an unbounded batch machine to minimize the maximum lateness. An unbounded batch machine is a machine that can process up to b (b ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is the time required for processing...
Process algebra provides essential tools for studying concurrent systems. An important branch of process algebra is value passing CCS. However, value passing CCS lacks not only action refinement, which is an essential operation in the design of concurrent systems, but also non-interleaving semantics, which is appropriate to specify the partial order and equivalence relations. In this paper, we will...
With the development of network and distributed systems, more and more security protocols rely heavily on time stamps, which are taken into account by a few formal methods. Generally, these methods use constraints to describe the characteristic of time variables. However, few of them give a feasible solution to the corresponding constraints solving problem. An effective framework to model and verify...
Tree-based algorithms, such as Patricia, LC-trie, LPFST, etc, are widely used to do longest prefix matching (LPM). These algorithms use all the bits of the prefix to build the tree and the bits are used from the most significant bit to the least significant bit sequentially. Thus the tree is not balanced and the tree depth is high. In this paper, we propose bit selection tree (BS-tree) to do LPM....
Decision tree construction is a well-studied problem in data mining. Recently, there has been much interest in mining data streams. Domingos and Hulten have presented a one-pass algorithm for decision tree constructions. Their system using Hoeffding inequality to achieve a probabilistic bound on the accuracy of the tree constructed. Gama et al. have extended VFDT in two directions. Their system VFDTc...
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.