OpenRaiser/Intern-Atlas huggingface dataset:
First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes
Venue: arXiv cs.NE 2012
Year: 2012

This paper extends a recently proposed model for combinatorial landscapes: Local Optima Networks (LON), to incorporate a first-improvement (greedy-ascent) hill-climbing algorithm, instead of a best-improvement (steepest-ascent) one, for the definition and extraction of the basins of attraction of the landscape optima. A statistical analysis comparing best and first improvement network models for a set of NK landscapes, is presented and discussed. Our results suggest structural differences between the two models with respect to both the network connectivity, and the nature of the basins of attraction. The impact of these differences in the behavior of search heuristics based on first and best improvement local search is thoroughly discussed.
Efficient Algorithms for Zeckendorf Arithmetic
Venue: arXiv cs.DS 2012
Year: 2012

We study the problem of addition and subtraction using the Zeckendorf representation of integers. We show that both operations can be performed in linear time; in fact they can be performed by combinational logic networks with linear size and logarithmic depth. The implications of these results for multiplication, division and square-root extraction are also discussed.
SiGMa: Simple Greedy Matching for Aligning Large Knowledge Bases
Venue: arXiv cs.AI 2012
Year: 2012

The Internet has enabled the creation of a growing number of large-scale knowledge bases in a variety of domains containing complementary information. Tools for automatically aligning these knowledge bases would make it possible to unify many sources of structured knowledge and answer complex queries. However, the efficient alignment of large-scale knowledge bases still poses a considerable challenge. Here, we present Simple Greedy Matching (SiGMa), a simple algorithm for aligning knowledge bases with millions of entities and facts. SiGMa is an iterative propagation algorithm which leverages both the structural information from the relationship graph as well as flexible similarity measures between entity properties in a greedy local search, thus making it scalable. Despite its greedy nature, our experiments indicate that SiGMa can efficiently match some of the world's largest knowledge bases with high precision. We provide additional experiments on benchmark datasets which demonstrate that SiGMa can outperform state-of-the-art approaches both in accuracy and efficiency.
Presentation an Approach for Optimization of Semantic Web Language Based on the Document Structure
Venue: arXiv cs.DB 2012
Year: 2012

Pattern tree are based on integrated rules which are equal to a combination of some points connected to each other in a hierarchical structure, called Enquiry Hierarchical (EH). The main operation in pattern enquiry seeking is to locate the steps that match the given EH in the dataset. A point of algorithms has offered for EH matching; but the majority of this algorithms seeks all of the enquiry steps to access all EHs in the dataset. A few algorithms such as seek only steps that satisfy end points of EH. All of above algorithms are trying to locate a way just for investigating direct testing of steps and to locate the answer of enquiry, directly via these points. In this paper, we describe a novel algorithm to locate the answer of enquiry without access to real point of the dataset blindly. In this algorithm, first, the enquiry will be executed on enquiry schema and this leads to a schema. Using this plan, it will be clear how to seek end steps and how to achieve enquiry dataset, before seeking of the dataset steps. Therefore, none of dataset steps will be seek blindly.
Quick HyperVolume
Venue: arXiv cs.DS 2012
Year: 2012

We present a new algorithm to calculate exact hypervolumes. Given a set of $d$-dimensional points, it computes the hypervolume of the dominated space. Determining this value is an important subroutine of Multiobjective Evolutionary Algorithms (MOEAs). We analyze the "Quick Hypervolume" (QHV) algorithm theoretically and experimentally. The theoretical results are a significant contribution to the current state of the art. Moreover the experimental performance is also very competitive, compared with existing exact hypervolume algorithms. A full description of the algorithm is currently submitted to IEEE Transactions on Evolutionary Computation.
A variant of list plus CRC concatenated polar code
Venue: arXiv cs.IT 2012
Year: 2012

A new family of codes based on polar codes, soft concatenation and list+CRC decoding is proposed. Numerical experiments show the performance competitive with industry standards and Tal, Vardy approach.
Complexity of Canadian Traveler Problem Variants
Venue: arXiv cs.CC 2012
Year: 2012

The Canadian traveler problem (CTP) is the problem of traversing a given graph, where some of the edges may be blocked - a state which is revealed only upon reaching an incident vertex. Originally stated by Papadimitriou and Yannakakis (1991), the adversarial version of CTP was shown to be PSPACE-complete, with the stochastic version shown to be #P-hard. We show that stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of stochastic CTP,and proceeding with gadgets that allow us to extend the proof to the independent case. Since for disjoint-path graphs, CTP can be solved in polynomial time, we examine the complexity of the more general remote-sensing CTP, and show that it is NP-hard even for disjoint-path graphs.
The Architecture of an Autonomic, Resource-Aware, Workstation-Based Distributed Database System
Venue: arXiv cs.DB 2012
Year: 2012

Distributed software systems that are designed to run over workstation machines within organisations are termed workstation-based. Workstation-based systems are characterised by dynamically changing sets of machines that are used primarily for other, user-centric tasks. They must be able to adapt to and utilize spare capacity when and where it is available, and ensure that the non-availability of an individual machine does not affect the availability of the system. This thesis focuses on the requirements and design of a workstation-based database system, which is motivated by an analysis of existing database architectures that are typically run over static, specially provisioned sets of machines. A typical clustered database system -- one that is run over a number of specially provisioned machines -- executes queries interactively, returning a synchronous response to applications, with its data made durable and resilient to the failure of machines. There are no existing workstation-based databases. Furthermore, other workstation-based systems do not attempt to achieve the requirements of interactivity and durability, because they are typically used to execute asynchronous batch processing jobs that tolerate data loss -- results can be re-computed. These systems use external servers to store the final results of computations rather than workstation machines. This thesis describes the design and implementation of a workstation-based database system and investigates its viability by evaluating its performance against existing clustered database systems and testing its availability during machine failures.
Kernel Bounds for Structural Parameterizations of Pathwidth
Venue: arXiv cs.DS 2012
Year: 2012

Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters. Our main result is that, unless NP is in coNP/poly, Pathwidth admits no polynomial kernelization even when parameterized by the vertex deletion distance to a clique, by giving a cross-composition from Cutwidth. The cross-composition works also for Treewidth, improving over previous lower bounds by the present authors. For Pathwidth, our result rules out polynomial kernels with respect to the distance to various classes of polynomial-time solvable inputs, like interval or cluster graphs. This leads to the question whether there are nontrivial structural parameters for which Pathwidth does admit a polynomial kernelization. To answer this, we give a collection of graph reduction rules that are safe for Pathwidth. We analyze the success of these results and obtain polynomial kernelizations with respect to the following parameters: the size of a vertex cover of the graph, the vertex deletion distance to a graph where each connected component is a star, and the vertex deletion distance to a graph where each connected component has at most c vertices.
A Methodology to manage victim components using CBO measure
Venue: arXiv cs.SE 2012
Year: 2012

The current practices of software industry demands development of a software within time and budget which is highly productive. The traditional approach of developing a software from scratch requires considerable amount of effort. To overcome the drawback a reuse drive software development approach is adopted. However there is a dire need for realizing effective software reuse. This paper presents several measures of reusability and presents a methodology of reconfiguring the victim components. The CBO measure helps in identifying the component to be reconfigured. The proposed strategy is simulated using HR portal domain specific component system.
Ontology for Cellular Communication
Venue: arXiv cs.SE 2012
Year: 2012

The lack of interoperability between mobile cellular access networks has long been a challenging obstacle, which telecommunication engineering is trying to overcome. In second generation networks for example, this problem lies in the fact that there are multiple standards. Each of these standards can operate in the same frequency range. However, each utilizes a different Radio Technology and Modulation Scheme, which are characteristics of the standard. Therefore, the lack of interoperability in 2G occurs because of the lack of standardization. Interoperability within 3G networks is limited to a few operating modes using different Radio Transmission Technologies that are not inter-operable. Thus, interoperability remains an issue for 3G. 4G technology even being successful in its various trials cannot guarantee the interoperability. This is within each network generation; meanwhile between heterogeneous network generations the situation seems to be worst. This approach is first to analyze the structure, inputs, and outputs of three different cellular technologies, performing a domain analysis (of this subset of technologies) and producing a feature model of the domain. Finally, we sought to build an ontology capable of providing a common view of the domain, providing an effective representation of relations between representations of corresponding concepts in different cellular technologies.
Variance Based Algorithm for Grouped-Subcarrier Allocation in OFDMA Wireless Systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a reduced complexity algorithm is proposed for grouped-subcarriers and power allocation in the downlink of OFDMA packet access wireless systems. The available subcarriers for data communication are grouped into partitions (groups) where each group is defined as a subchannel. The scheduler located at the base station allocates subchannels to users based on the variance of subchannel gains. The proposed algorithm for group allocation is a two-step algorithm that allocates groups to users based on the descending order of their variances to resolve the conflicting selection problem, followed by a step of fairness proportionality enhancement. To reduce the feedback burden and the complexity of the power allocation algorithm, each user feeds back the CSI on each group if the variance of gains of subcarriers inside it is less than a predefined threshold. To Show the performance of the proposed scheme, a selection of simulation results is presented.
Stator flux optimization on direct torque control with fuzzy logic
Venue: arXiv cs.AI 2012
Year: 2012

The Direct Torque Control (DTC) is well known as an effective control technique for high performance drives in a wide variety of industrial applications and conventional DTC technique uses two constant reference value: torque and stator flux. In this paper, fuzzy logic based stator flux optimization technique for DTC drives that has been proposed. The proposed fuzzy logic based stator flux optimizer self-regulates the stator flux reference using induction motor load situation without need of any motor parameters. Simulation studies have been carried out with Matlab/Simulink to compare the proposed system behaviors at vary load conditions. Simulation results show that the performance of the proposed DTC technique has been improved and especially at low-load conditions torque ripple are greatly reduced with respect to the conventional DTC.
Clown: a Microprocessor Simulator for Operating System Studies
Venue: arXiv cs.OH 2012
Year: 2012

In this paper, I present the design and implementation of Clown--a simulator of a microprocessor-based computer system specifically optimized for teaching operating system courses at undergraduate or graduate levels. The package includes the simulator itself, as well as a collection of basic I/O devices, an assembler, a linker, and a disk formatter. The simulator architecturally resembles mainstream microprocessors from the Intel 80386 family, but is much easier to learn and program. The simulator is fast enough to be used as an emulator--in the direct user interaction mode.
The total irregularity of a graph
Venue: arXiv cs.DM 2012
Year: 2012

In this note a new measure of irregularity of a simple undirected graph $G$ is introduced. It is named the total irregularity of a graph and is defined as $\irr_t(G) = 1/2\sum_{u,v \in V(G)} |d_G(u)-d_G(v)|$, where $d_G(u)$ denotes the degree of a vertex $u \in V(G)$. The graphs with maximal total irregularity are determined. It is also shown that among all trees of same order the star graph has the maximal total irregularity.
Basic Network Creation Games with Communication Interests
Venue: arXiv cs.GT 2012
Year: 2012

Network creation games model the creation and usage costs of networks formed by a set of selfish peers. Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links. In doing so, a peer can reduce its individual communication cost. Typically, these costs are modeled by the maximum or average distance in the network. We introduce a generalized version of the basic network creation game (BNCG). In the BNCG (by Alon et al., SPAA 2010), each peer may replace one of its incident links by a link to an arbitrary peer. This is done in a selfish way in order to minimize either the maximum or average distance to all other peers. That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers. However, participants of large networks are seldom interested in all peers. Rather, they want to communicate efficiently only with a small subset of peers. Our model incorporates these (communication) interests explicitly. In the MAX-version, each node tries to minimize its maximum distance to nodes it is interested in. Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model. For the MAX-version, we give an upper worst case bound of O(\sqrt{n}) for the private costs in an equilibrium of n peers. Moreover, we give an equilibrium for a circular interest graph where a node has private cost Ω(\sqrt{n}), showing that our bound is tight. This example can be extended such that we get a tight bound of Θ(\sqrt{n}) for the price of anarchy. For the case of general communication networks we show the price of anarchy to be Θ(n). Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.
Using mobile agent results to create hard-to-detect computer viruses
Venue: arXiv cs.CR 2012
Year: 2012

The theory of computer viruses has been studied by several authors, though there is no systematic theoretical study up to now. The long time open question in this area is as follows: Is it possible to design a signature-free (including dynamic signatures which we will define late) virus? In this paper, we give an affirmative answer to this question from a theoretical viewpoint. We will introduce a new stronger concept: dynamic signatures of viruses, and present a method to design viruses which are static signature-free and whose dynamic signatures are hard to determine unless some cryptographic assumption fails. We should remark that our results are only for theoretical interest and may be resource intensive in practice.
A Simplified Min-Sum Decoding Algorithm for Non-Binary LDPC Codes
Venue: arXiv cs.IT 2012
Year: 2012

Non-binary low-density parity-check codes are robust to various channel impairments. However, based on the existing decoding algorithms, the decoder implementations are expensive because of their excessive computational complexity and memory usage. Based on the combinatorial optimization, we present an approximation method for the check node processing. The simulation results demonstrate that our scheme has small performance loss over the additive white Gaussian noise channel and independent Rayleigh fading channel. Furthermore, the proposed reduced-complexity realization provides significant savings on hardware, so it yields a good performance-complexity tradeoff and can be efficiently implemented.
Evolving Musical Counterpoint: The Chronopoint Musical Evolution System
Venue: arXiv cs.SD 2012
Year: 2012

Musical counterpoint, a musical technique in which two or more independent melodies are played simultaneously with the goal of creating harmony, has been around since the baroque era. However, to our knowledge computational generation of aesthetically pleasing linear counterpoint based on subjective fitness assessment has not been explored by the evolutionary computation community (although generation using objective fitness has been attempted in quite a few cases). The independence of contrapuntal melodies and the subjective nature of musical aesthetics provide an excellent platform for the application of genetic algorithms. In this paper, a genetic algorithm approach to generating contrapuntal melodies is explained, with a description of the various musical heuristics used and of how variable-length chromosome strings are used to avoid generating "jerky" rhythms and melodic phrases, as well as how subjectivity is incorporated into the algorithm's fitness measures. Next, results from empirical testing of the algorithm are presented, with a focus on how a user's musical sophistication influences their experience. Lastly, further musical and compositional applications of the algorithm are discussed along with planned future work on the algorithm.
VOI-aware MCTS
Venue: arXiv cs.AI 2012
Year: 2012

UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS) in games and Markov decision processes, is based on UCB1, a sampling policy for the Multi-armed Bandit problem (MAB) that minimizes the cumulative regret. However, search differs from MAB in that in MCTS it is usually only the final "arm pull" (the actual move selection) that collects a reward, rather than all "arm pulls". In this paper, an MCTS sampling policy based on Value of Information (VOI) estimates of rollouts is suggested. Empirical evaluation of the policy and comparison to UCB1 and UCT is performed on random MAB instances as well as on Computer Go.
Bin Packing/Covering with Delivery: Some variations, theoretical results and efficient offline algorithms
Venue: arXiv cs.DS 2012
Year: 2012

In the recent paper \cite{BDT10} we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a "good and fast" packing or covering. In that paper we mainly dealt with only one possible online BP/CD model, and proposed a new method that we call the Evolution of Algorithms. In case of such methods a neighborhood structure is defined among algorithms, and using a metaheuristic (for example simulated annealing) in some sense the best algorithm is chosen to solve the problem. Now we turn to investigate the offline case. We define several ways to treat such a BP/CD problem, although we investigate only one of them here. For the analysis, a novel view on "offline optimum" is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an approximation ratio better than 6/7 if $P\ne NP$.
A Review of routing protocols for mobile cognitive radio ad hoc networks
Venue: arXiv cs.NI 2012
Year: 2012

Ad hoc network is a collection of wireless mobile nodes that dynamically form a temporary network without the use of any existing network infrastructure or centralized administration. A cognitive radio is a radio that can change its transmitter parameters based on interaction with the environment in which it operates. The basic idea of cognitive radio networks is that the unlicensed devices (cognitive radio users or secondary users) need to vacate the spectrum band once the licensed device (primary user) is detected. Cognitive capability and reconfigurability are the key characteristics of cognitive radio. Routing is an important issue in Mobile Cognitive Radio Ad Hoc Networks (MCRAHNs). In this paper, a survey of routing protocols for mobile cognitive radio ad networks is discussed.
Delay Stability Regions of the Max-Weight Policy under Heavy-Tailed Traffic
Venue: arXiv cs.SY 2012
Year: 2012

We carry out a delay stability analysis (i.e., determine conditions under which expected steady-state delays at a queue are finite) for a simple 3-queue system operated under the Max-Weight scheduling policy, for the case where one of the queues is fed by heavy-tailed traffic (i.e, when the number of arrivals at each time slot has infinite second moment). This particular system exemplifies an intricate phenomenon whereby heavy-tailed traffic at one queue may or may not result in the delay instability of another queue, depending on the arrival rates. While the ordinary stability region (in the sense of convergence to a steady-state distribution) is straightforward to determine, the determination of the delay stability region is more involved: (i) we use "fluid-type" sample path arguments, combined with renewal theory, to prove delay instability outside a certain region; (ii) we use a piecewise linear Lyapunov function to prove delay stability in the interior of that same region; (iii) as an intermediate step in establishing delay stability, we show that the expected workload of a stable M/GI/1 queue scales with time as $\mathcal{O}(t^{1/(1+γ)})$, assuming that service times have a finite $1+γ$ moment, where $γ\in (0,1)$.