OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Heuristic-Based Artificial Immune System for Task Scheduling
Venue: arXiv cs.DC 2011
Year: 2011

Task scheduling problem in heterogeneous systems is the process of allocating tasks of an application to heterogeneous processors interconnected by high-speed networks, so that minimizing the finishing time of application as much as possible. Tasks are processing units of application and have precedenceconstrained, communication and also, are presented by Directed Acyclic Graphs (DAGs). Evolutionary algorithms are well suited for solving task scheduling problem in heterogeneous environment. In this paper, we propose a hybrid heuristic-based Artificial Immune System (AIS) algorithm for solving the scheduling problem. In this regard, AIS with some heuristics and Single Neighbourhood Search (SNS) technique are hybridized. Clonning and immune-remove operators of AIS provide diversity, while heuristics and SNS provide convergence of algorithm into good solutions, that is balancing between exploration and exploitation. We have compared our method with some state-of-the art algorithms. The results of the experiments show the validity and efficiency of our method.
Multiple Traveling Salesmen in Asymmetric Metrics
Venue: arXiv cs.DS 2011
Year: 2011

We consider some generalizations of the Asymmetric Traveling Salesman Path problem. Suppose we have an asymmetric metric G = (V,A) with two distinguished nodes s,t. We are also given a positive integer k. The goal is to find k paths of minimum total cost from s to t whose union spans all nodes. We call this the k-Person Asymmetric Traveling Salesmen Path problem (k-ATSPP). Our main result for k-ATSPP is a bicriteria approximation that, for some parameter b >= 1 we may choose, finds between k and k + k/b paths of total length O(b log |V|) times the optimum value of an LP relaxation based on the Held-Karp relaxation for the Traveling Salesman problem. On one extreme this is an O(log |V|)-approximation that uses up to 2k paths and on the other it is an O(k log |V|)-approximation that uses exactly k paths. Next, we consider the case where we have k pairs of nodes (s_1,t_1), ..., (s_k,t_k). The goal is to find an s_i-t_i path for every pair such that each node of G lies on at least one of these paths. Simple approximation algorithms are presented for the special cases where the metric is symmetric or where s_i = t_i for each i. We also show that the problem can be approximated within a factor O(log n) when k=2. On the other hand, we demonstrate that the general problem cannot be approximated within any bounded ratio unless P = NP.
Period Estimation in Astronomical Time Series Using Slotted Correntropy
Venue: arXiv cs.IT 2011
Year: 2011

In this letter, we propose a method for period estimation in light curves from periodic variable stars using correntropy. Light curves are astronomical time series of stellar brightness over time, and are characterized as being noisy and unevenly sampled. We propose to use slotted time lags in order to estimate correntropy directly from irregularly sampled time series. A new information theoretic metric is proposed for discriminating among the peaks of the correntropy spectral density. The slotted correntropy method outperformed slotted correlation, string length, VarTools (Lomb-Scargle periodogram and Analysis of Variance), and SigSpec applications on a set of light curves drawn from the MACHO survey.
Isomorphisms of types in the presence of higher-order references
Venue: arXiv cs.LO 2011
Year: 2011

We investigate the problem of type isomorphisms in a programming language with higher-order references. We first recall the game-theoretic model of higher-order references by Abramsky, Honda and McCusker. Solving an open problem by Laurent, we show that two finitely branching arenas are isomorphic if and only if they are geometrically the same, up to renaming of moves (Laurent's forest isomorphism). We deduce from this an equational theory characterizing isomorphisms of types in a finitary language with higher order references. We show however that Laurent's conjecture does not hold on infinitely branching arenas, yielding a non-trivial type isomorphism in the extension of this language with natural numbers.
Polytope Codes Against Adversaries in Networks
Venue: arXiv cs.IT 2011
Year: 2011

Network coding is studied when an adversary controls a subset of nodes in the network of limited quantity but unknown location. This problem is shown to be more difficult than when the adversary controls a given number of edges in the network, in that linear codes are insufficient. To solve the node problem, the class of Polytope Codes is introduced. Polytope Codes are constant composition codes operating over bounded polytopes in integer vector fields. The polytope structure creates additional complexity, but it induces properties on marginal distributions of code vectors so that validities of codewords can be checked by internal nodes of the network. It is shown that Polytope Codes achieve a cut-set bound for a class of planar networks. It is also shown that this cut-set bound is not always tight, and a tighter bound is given for an example network.
The Biequivalence of Locally Cartesian Closed Categories and Martin-Löf Type Theories
Venue: arXiv cs.LO 2011
Year: 2011

Seely's paper "Locally cartesian closed categories and type theory" contains a well-known result in categorical type theory: that the category of locally cartesian closed categories is equivalent to the category of Martin-Löf type theories with Pi-types, Sigma-types and extensional identity types. However, Seely's proof relies on the problematic assumption that substitution in types can be interpreted by pullbacks. Here we prove a corrected version of Seely's theorem: that the Bénabou-Hofmann interpretation of Martin-Löf type theory in locally cartesian closed categories yields a biequivalence of 2-categories. To facilitate the technical development we employ categories with families as a substitute for syntactic Martin-Löf type theories. As a second result we prove that if we remove Pi-types the resulting categories with families are biequivalent to left exact categories.
Insights from Classifying Visual Concepts with Multiple Kernel Learning
Venue: arXiv cs.CV 2011
Year: 2011

Combining information from various image features has become a standard technique in concept recognition tasks. However, the optimal way of fusing the resulting kernel functions is usually unknown in practical applications. Multiple kernel learning (MKL) techniques allow to determine an optimal linear combination of such similarity matrices. Classical approaches to MKL promote sparse mixtures. Unfortunately, so-called 1-norm MKL variants are often observed to be outperformed by an unweighted sum kernel. The contribution of this paper is twofold: We apply a recently developed non-sparse MKL variant to state-of-the-art concept recognition tasks within computer vision. We provide insights on benefits and limits of non-sparse MKL and compare it against its direct competitors, the sum kernel SVM and the sparse MKL. We report empirical results for the PASCAL VOC 2009 Classification and ImageCLEF2010 Photo Annotation challenge data sets. About to be submitted to PLoS ONE.
Single Time-Stamped Tries for Retroactive Call Subsumption
Venue: arXiv cs.PL 2011
Year: 2011

Tabling is an evaluation strategy for Prolog programs that works by storing answers in a table space and then by using them in similar subgoals. Some tabling engines use call by subsumption, where it is determined that a subgoal will consume answers from a more general subgoal in order to reduce the search space and increase efficiency. We designed an extension, named Retroactive Call Subsumption (RCS), that implements call by subsumption independently of the call order, thus allowing a more general subgoal to force previous called subgoals to become answer consumers. For this extension, we propose a new table space design, the Single Time Stamped Trie (STST), that is organized to make answer sharing across subsumed/subsuming subgoals simple and efficient. In this paper, we present the new STST table space design and we discuss the main modifications made to the original Time Stamped Tries approach to non-retroactive call by subsumption. In experimental results, with programs that stress some deficiencies of the new STST design, some overheads may be observed, however the results achieved with more realistic programs greatly offset these overheads.
Note on fast division algorithm for polynomials using Newton iteration
Venue: arXiv cs.SC 2011
Year: 2011

The classical division algorithm for polynomials requires $O(n^2)$ operations for inputs of size $n$. Using reversal technique and Newton iteration, it can be improved to $O({M}(n))$, where ${M}$ is a multiplication time. But the method requires that the degree of the modulo, $x^l$, should be the power of 2. If $l$ is not a power of 2 and $f(0)=1$, Gathen and Gerhard suggest to compute the inverse,$f^{-1}$, modulo $x^{\lceil l/2^r\rceil}, x^{\lceil l/2^{r-1}\rceil},..., x^{\lceil l/2\rceil}, x^l$, separately. But they did not specify the iterative step. In this note, we show that the original Newton iteration formula can be directly used to compute $f^{-1}\,{mod}\,x^{l}$ without any additional cost, when $l$ is not a power of 2.
Mobile IP and protocol authentication extension
Venue: arXiv cs.CR 2011
Year: 2011

Mobile IP is an open standard, defined by the Internet Engineering Task Force (IETF) RFC 3220. By using Mobile IP, you can keep the same IP address, stay connected, and maintain ongoing applications while roaming between IP networks. Mobile IP is scalable for the Internet because it is based on IP - any media that can support IP can support Mobile IP.
Legal Resources Information System for Information Agencies of Specialized Libraries
Venue: arXiv cs.DL 2011
Year: 2011

In recent years, the rapid development of information technology and communication has a strong impact to industry information - the library. The mission of the industry when in fact the great social place to see the library as knowledge management. Vietnam is in the process of building the rule of law socialist orientation and improves the legal system. So in the current development process, the law library plays an important role in the retention, dissemination and provision of legal information service of legislative, executive and judiciary, particularly especially research, teaching and learning of law school. But the response of the legal information library information agencies remains limited compared to the increasing demand of users.
Distributed Source Localization in Wireless Underground Sensor Networks
Venue: arXiv cs.IT 2011
Year: 2011

Node localization plays an important role in many practical applications of wireless underground sensor networks (WUSNs), such as finding the locations of earthquake epicenters, underground explosions, and microseismic events in mines. It is more difficult to obtain the time-difference-of-arrival (TDOA) measurements in WUSNs than in terrestrial wireless sensor networks because of the unfavorable channel characteristics in the underground environment. The robust Chinese remainder theorem (RCRT) has been shown to be an effective tool for solving the phase ambiguity problem and frequency estimation problem in wireless sensor networks. In this paper, the RCRT is used to robustly estimate TDOA or range difference in WUSNs and therefore improves the ranging accuracy in such networks. After obtaining the range difference, distributed source localization algorithms based on a diffusion strategy are proposed to decrease the communication cost while satisfying the localization accuracy requirement. Simulation results confirm the validity and efficiency of the proposed methods.
Performance Evaluation of Road Traffic Control Using a Fuzzy Cellular Model
Venue: arXiv cs.AI 2011
Year: 2011

In this paper a method is proposed for performance evaluation of road traffic control systems. The method is designed to be implemented in an on-line simulation environment, which enables optimisation of adaptive traffic control strategies. Performance measures are computed using a fuzzy cellular traffic model, formulated as a hybrid system combining cellular automata and fuzzy calculus. Experimental results show that the introduced method allows the performance to be evaluated using imprecise traffic measurements. Moreover, the fuzzy definitions of performance measures are convenient for uncertainty determination in traffic control decisions.
A real time vehicles detection algorithm for vision based sensors
Venue: arXiv cs.CV 2011
Year: 2011

A vehicle detection plays an important role in the traffic control at signalised intersections. This paper introduces a vision-based algorithm for vehicles presence recognition in detection zones. The algorithm uses linguistic variables to evaluate local attributes of an input image. The image attributes are categorised as vehicle, background or unknown features. Experimental results on complex traffic scenes show that the proposed algorithm is effective for a real-time vehicles detection.
Vehicles Recognition Using Fuzzy Descriptors of Image Segments
Venue: arXiv cs.CV 2011
Year: 2011

In this paper a vision-based vehicles recognition method is presented. Proposed method uses fuzzy description of image segments for automatic recognition of vehicles recorded in image data. The description takes into account selected geometrical properties and shape coefficients determined for segments of reference image (vehicle model). The proposed method was implemented using reasoning system with fuzzy rules. A vehicles recognition algorithm was developed based on the fuzzy rules describing shape and arrangement of the image segments that correspond to visible parts of a vehicle. An extension of the algorithm with set of fuzzy rules defined for different reference images (and various vehicle shapes) enables vehicles classification in traffic scenes. The devised method is suitable for application in video sensors for road traffic control and surveillance systems.
Closed-Form Bounds to the Rice and Incomplete Toronto Functions and Incomplete Lipschitz-Hankel Integrals
Venue: arXiv cs.IT 2011
Year: 2011

This article provides novel analytical results for the Rice function, the incomplete Toronto function and the incomplete Lipschitz-Hankel Integrals. Firstly, upper and lower bounds are derived for the Rice function, $Ie(k,x)$. Secondly, explicit expressions are derived for the incomplete Toronto function, $T_{B}(m,n,r)$, and the incomplete Lipschitz-Hankel Integrals of the modified Bessel function of the first kind, $Ie_{μ,n}(a,z)$, for the case that $n$ is an odd multiple of 0.5 and $m \geq n$. By exploiting these expressions, tight upper and lower bounds are subsequently proposed for both $T_{B}(m,n,r)$ function and $Ie_{μ,n}(a,z)$ integrals. Importantly, all new representations are expressed in closed-form whilst the proposed bounds are shown to be rather tight. Based on these features, it is evident that the offered results can be utilized effectively in analytical studies related to wireless communications. Indicative applications include, among others, the performance evaluation of digital communications over fading channels and the information-theoretic analysis of multiple-input multiple-output systems.
On Accuracy of Community Structure Discovery Algorithms
Venue: arXiv cs.SI 2011
Year: 2011

Community structure discovery in complex networks is a quite challenging problem spanning many applications in various disciplines such as biology, social network and physics. Emerging from various approaches numerous algorithms have been proposed to tackle this problem. Nevertheless little attention has been devoted to compare their efficiency on realistic simulated data. To better understand their relative performances, we evaluate systematically eleven algorithms covering the main approaches. The Normalized Mutual Information (NMI) measure is used to assess the quality of the discovered community structure from controlled artificial networks with realistic topological properties. Results show that along with the network size, the average proportion of intra-community to inter-community links is the most influential parameter on performances. Overall, "Infomap" is the leading algorithm, followed by "Walktrap", "SpinGlass" and "Louvain" which also achieve good consistency.
Joint Network Coding for Interfering Wireless Multicast Networks
Venue: arXiv cs.IT 2011
Year: 2011

Interference in wireless networks is one of the key-capacity limiting factor. The multicast capacity of an ad- hoc wireless network decreases with an increasing number of transmitting and/or receiving nodes within a fixed area. Digital Network Coding (DNC) has been shown to improve the multicast capacity of non-interfering wireless network. However recently proposed Physical-layer Network Coding (PNC) and Analog Network Coding (ANC) has shown that it is possible to decode an unknown packet from the collision of two packet, when one of the colliding packet is known a priori. Taking advantage of such collision decoding scheme, in this paper we propose a Joint Network Coding based Cooperative Retransmission (JNC- CR) scheme, where we show that ANC along with DNC can offer a much higher retransmission gain than that attainable through either ANC, DNC or Automatic Repeat reQuest (ARQ) based retransmission. This scheme can be applied for two wireless multicast groups interfering with each other. Because of the broadcast nature of the wireless transmission, receivers of different multicast group can opportunistically listen and cache packets from the interfering transmitter. These cached packets, along with the packets the receiver receives from its transmitter can then be used for decoding the JNC packet. We validate the higher retransmission gain performance of JNC with an optimal DNC scheme, using simulation.
A Distributed Scheduling Algorithm for High-Speed Switching Systems
Venue: arXiv cs.NI 2011
Year: 2011

Given the rapid increase in traffic, greater demands have been put on research in high-speed switching systems. Such systems have to simultaneously meet several constraints, e.g., high throughput, low delay and low complexity. This makes it challenging to design an efficient scheduling algorithm, and has consequently drawn considerable research interest. However, previous results either cannot provide a 100% throughput guarantee without a speedup, or require a complex centralized scheduler. In this paper, we design a distributed 100% throughput algorithm for crosspoint buffered switches, called DISQUO, with very limited message passing. We prove that DISQUO can achieve 100% throughput for any admissible Bernoulli traffic, with a low time complexity of O(1) per port and a few bits message exchanging in every time slot. To the best of our knowledge, it is the first distributed algorithm that can provide a 100% throughput for a crosspoint buffered switch.
Performance Analysis of Enhanced Clustering Algorithm for Gene Expression Data
Venue: arXiv cs.LG 2011
Year: 2011

Microarrays are made it possible to simultaneously monitor the expression profiles of thousands of genes under various experimental conditions. It is used to identify the co-expressed genes in specific cells or tissues that are actively used to make proteins. This method is used to analysis the gene expression, an important task in bioinformatics research. Cluster analysis of gene expression data has proved to be a useful tool for identifying co-expressed genes, biologically relevant groupings of genes and samples. In this paper we applied K-Means with Automatic Generations of Merge Factor for ISODATA- AGMFI. Though AGMFI has been applied for clustering of Gene Expression Data, this proposed Enhanced Automatic Generations of Merge Factor for ISODATA- EAGMFI Algorithms overcome the drawbacks of AGMFI in terms of specifying the optimal number of clusters and initialization of good cluster centroids. Experimental results on Gene Expression Data show that the proposed EAGMFI algorithms could identify compact clusters with perform well in terms of the Silhouette Coefficients cluster measure.
A Scalable Multiclass Algorithm for Node Classification
Venue: arXiv cs.LG 2011
Year: 2011

We introduce a scalable algorithm, MUCCA, for multiclass node classification in weighted graphs. Unlike previously proposed methods for the same task, MUCCA works in time linear in the number of nodes. Our approach is based on a game-theoretic formulation of the problem in which the test labels are expressed as a Nash Equilibrium of a certain game. However, in order to achieve scalability, we find the equilibrium on a spanning tree of the original graph. Experiments on real-world data reveal that MUCCA is much faster than its competitors while achieving a similar predictive performance.
Simulation-based study of MPTCP (Multipath TCP)
Venue: arXiv cs.NI 2011
Year: 2011

Our current world is revolutionned by the networks which are interconnecting any machine to any other one. Nowadays equipments are plugged to the network by the way of many different network adapters (Ethernet, wifi, GSM), and network equipments are more and more interconnected to each other creating a highly mesh network. Thus, redundant paths are created between any two endpoints enabling multipath or the use of multiple paths to handle a communication. The benefits of multipath are the enhancement of robustness against failure, and minimizing communication cost. In the present work, we will talk about some solutions of multipath applied to the transport level. We will expose the most important problem facing multipath which is packet reordering, and we will also expose results of our simulations.
Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm
Venue: arXiv cs.CG 2011
Year: 2011

We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with Theta(n^2) additional coordinate planes between every two such grid planes.