OpenRaiser/Intern-Atlas huggingface dataset:
Hyper heuristic based on great deluge and its variants for exam timetabling problem
Venue: arXiv cs.AI 2012
Year: 2012

Today, University Timetabling problems are occurred annually and they are often hard and time consuming to solve. This paper describes Hyper Heuristics (HH) method based on Great Deluge (GD) and its variants for solving large, highly constrained timetabling problems from different domains. Generally, in hyper heuristic framework, there are two main stages: heuristic selection and move acceptance. This paper emphasizes on the latter stage to develop Hyper Heuristic (HH) framework. The main contribution of this paper is that Great Deluge (GD) and its variants: Flex Deluge(FD), Non-linear(NLGD), Extended Great Deluge(EGD) are used as move acceptance method in HH by combining Reinforcement learning (RL).These HH methods are tested on exam benchmark timetabling problem and best results and comparison analysis are reported.
Note on RIP-based Co-sparse Analysis
Venue: arXiv cs.IT 2012
Year: 2012

Over the past years, there are increasing interests in recovering the signals from undersampling data where such signals are sparse under some orthogonal dictionary or tight framework, which is referred to be sparse synthetic model. More recently, its counterpart, i.e., the sparse analysis model, has also attracted researcher's attentions where many practical signals which are sparse in the truly redundant dictionary are concerned. This short paper presents important complement to the results in existing literatures for treating sparse analysis model. Firstly, we give the natural generalization of well-known restricted isometry property (RIP) to deal with sparse analysis model, where the truly arbitrary incoherent dictionary is considered. Secondly, we studied the theoretical guarantee for the accurate recovery of signal which is sparse in general redundant dictionaries through solving l1-norm sparsity-promoted optimization problem. This work shows not only that compressed sensing is viable in the context of sparse analysis, but also that accurate recovery is possible via solving l1-minimization problem.
Curves on torus layers and coding for continuous alphabet sources
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the problem of transmitting a continuous alphabet discrete-time source over an AWGN channel. The design of good curves for this purpose relies on geometrical properties of spherical codes and projections of $N$-dimensional lattices. We propose a constructive scheme based on a set of curves on the surface of a 2N-dimensional sphere and present comparisons with some previous works.
Temporal Analysis of Literary and Programming Prose
Venue: arXiv cs.SE 2012
Year: 2012

Literary works reference a variety of globally shared themes including well-known people, events, and time periods. It is particularly interesting to locate patterns that are either invariant across time or exhibit a characteristic change across time, as they could imply something important about society that those works record. This paper suggests the use of Google n-gram viewer as a fast prototyping method for examining time-based properties over a rich sample of literary prose. Using this method, we find that some repeating periods of time, like Sunday, are referenced disproportionally, allowing us to pose questions such as why a day like Thursday is so unpopular. Furthermore, by treating software as a work of prose, we can apply a similar analysis to open-source software repositories and explore time-based relations in commit logs. Doing a simple statistical analysis on a few temporal keywords in the log records, we reinforce and weaken a few beliefs on how college students approach open source software. Finally, we help readers working on their own temporal analysis by comparing the fundamental differences between literary works and code repositories, and suggest blog or wiki as recently-emerging works.
Choosing Products in Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

We study the consequences of adopting products by agents who form a social network. To this end we use the threshold model introduced in Apt and Markakis, arXiv:1105.2434, in which the nodes influenced by their neighbours can adopt one out of several alternatives, and associate with such each social network a strategic game between the agents. The possibility of not choosing any product results in two special types of (pure) Nash equilibria. We show that such games may have no Nash equilibrium and that determining the existence of a Nash equilibrium, also of a special type, is NP-complete. The situation changes when the underlying graph of the social network is a DAG, a simple cycle, or has no source nodes. For these three classes we determine the complexity of establishing whether a (special type of) Nash equilibrium exists. We also clarify for these categories of games the status and the complexity of the finite improvement property (FIP). Further, we introduce a new property of the uniform FIP which is satisfied when the underlying graph is a simple cycle, but determining it is co-NP-hard in the general case and also when the underlying graph has no source nodes. The latter complexity results also hold for verifying the property of being a weakly acyclic game.
Achieving Global Optimality for Weighted Sum-Rate Maximization in the K-User Gaussian Interference Channel with Multiple Antennas
Venue: arXiv cs.IT 2012
Year: 2012

Characterizing the global maximum of weighted sum-rate (WSR) for the K-user Gaussian interference channel (GIC), with the interference treated as Gaussian noise, is a key problem in wireless communication. However, due to the users' mutual interference, this problem is in general non-convex and thus cannot be solved directly by conventional convex optimization techniques. In this paper, by jointly utilizing the monotonic optimization and rate profile techniques, we develop a new framework to obtain the globally optimal power control and/or beamforming solutions to the WSR maximization problems for the GICs with single-antenna transmitters and single-antenna receivers (SISO), single-antenna transmitters and multi-antenna receivers (SIMO), or multi-antenna transmitters and single-antenna receivers (MISO). Different from prior work, this paper proposes to maximize the WSR in the achievable rate region of the GIC directly by exploiting the facts that the achievable rate region is a "normal" set and the users' WSR is a "strictly increasing" function over the rate region. Consequently, the WSR maximization is shown to be in the form of monotonic optimization over a normal set and thus can be solved globally optimally by the existing outer polyblock approximation algorithm. However, an essential step in the algorithm hinges on how to efficiently characterize the intersection point on the Pareto boundary of the achievable rate region with any prescribed "rate profile" vector. This paper shows that such a problem can be transformed into a sequence of signal-to-interference-plus-noise ratio (SINR) feasibility problems, which can be solved efficiently by existing techniques. Numerical results validate that the proposed algorithms can achieve the global WSR maximum for the SISO, SIMO or MISO GIC.
Supervised Learning in Multilayer Spiking Neural Networks
Venue: arXiv cs.NE 2012
Year: 2012

The current article introduces a supervised learning algorithm for multilayer spiking neural networks. The algorithm presented here overcomes some limitations of existing learning algorithms as it can be applied to neurons firing multiple spikes and it can in principle be applied to any linearisable neuron model. The algorithm is applied successfully to various benchmarks, such as the XOR problem and the Iris data set, as well as complex classifications problems. The simulations also show the flexibility of this supervised learning algorithm which permits different encodings of the spike timing patterns, including precise spike trains encoding.
Approximate Distance Oracles with Improved Query Time
Venue: arXiv cs.DM 2012
Year: 2012

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\geq 2$, we show that a $(2k-1)$-approximate distance oracle for $G$ of size $O(kn^{1 + 1/k})$ and with $O(\log k)$ query time can be constructed in $O(\min\{kmn^{1/k},\sqrt km + kn^{1 + c/\sqrt k}\})$ time for some constant $c$. This improves the $O(k)$ query time of Thorup and Zwick. Furthermore, for any $0 < ε\leq 1$, we give an oracle of size $O(kn^{1 + 1/k})$ that answers $((2 + ε)k)$-approximate distance queries in $O(1/ε)$ time. At the cost of a $k$-factor in size, this improves the $128k$ approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erdős. We can match the $O(n^{1 + 1/k})$ size bound of Mendel and Naor for any constant $ε> 0$ and $k = O(\log n/\log\log n)$.
Optimal Linear Codes with a Local-Error-Correction Property
Venue: arXiv cs.IT 2012
Year: 2012

Motivated by applications to distributed storage, Gopalan \textit{et al} recently introduced the interesting notion of information-symbol locality in a linear code. By this it is meant that each message symbol appears in a parity-check equation associated with small Hamming weight, thereby enabling recovery of the message symbol by examining a small number of other code symbols. This notion is expanded to the case when all code symbols, not just the message symbols, are covered by such "local" parity. In this paper, we extend the results of Gopalan et. al. so as to permit recovery of an erased code symbol even in the presence of errors in local parity symbols. We present tight bounds on the minimum distance of such codes and exhibit codes that are optimal with respect to the local error-correction property. As a corollary, we obtain an upper bound on the minimum distance of a concatenated code.
An Improved XP Software Development Model
Venue: arXiv cs.SE 2012
Year: 2012

The concept of agile process models has attained great popularity in software (SW) development community in last few years. Agile models promote fast development. Fast development has certain drawbacks, such as weak documentation and performance for medium and large development projects. Fast development also promotes use of agile process models in small-scale projects. This paper modifies and evaluates Extreme Programming (XP) process model and proposes a novel process model based on these modifications.
Improvement of Key Problems of Software Testing in Quality Assurance
Venue: arXiv cs.SE 2012
Year: 2012

Quality assurance makes sure the project will be completed based on the previously approved specifications, standards and functionality. It is required without defects and possible problems. It monitors and tries to progress the development process from the start of the project. Software Quality Assurance (SQA) is the combination of the entire software development process, which includes software design, coding, source code control, code review, change management, configuration management and release management. In this paper we describe the solution for the key problems of software testing in quality assurance. The existing software practices have some problems such as testing practices, attitude of users and culture of organizations. All these tree problems have some combined problems such as shortcuts in testing, reduction in testing time, poor documentation etc. In this paper we are recommending strategies to provide solution of the said problems mentioned above.
Evolutionary Computation in Astronomy and Astrophysics: A Review
Venue: arXiv cs.AI 2012
Year: 2012

In general Evolutionary Computation (EC) includes a number of optimization methods inspired by biological mechanisms of evolution. The methods catalogued in this area use the Darwinian principles of life evolution to produce algorithms that returns high quality solutions to hard-to-solve optimization problems. The main strength of EC is precisely that they provide good solutions even if the computational resources (e.g., running time) are limited. Astronomy and Astrophysics are two fields that often require optimizing problems of high complexity or analyzing a huge amount of data and the so-called complete optimization methods are inherently limited by the size of the problem/data. For instance, reliable analysis of large amounts of data is central to modern astrophysics and astronomical sciences in general. EC techniques perform well where other optimization methods are inherently limited (as complete methods applied to NP-hard problems), and in the last ten years, numerous proposals have come up that apply with greater or lesser success methodologies of evolutional computation to common engineering problems. Some of these problems, such as the estimation of non-lineal parameters, the development of automatic learning techniques, the implementation of control systems, or the resolution of multi-objective optimization problems, have had (and have) a special repercussion in the fields. For these reasons EC emerges as a feasible alternative for traditional methods. In this paper, we discuss some promising applications in this direction and a number of recent works in this area; the paper also includes a general description of EC to provide a global perspective to the reader and gives some guidelines of application of EC techniques for future research
Message passing for quantified Boolean formulas
Venue: arXiv cs.AI 2012
Year: 2012

We introduce two types of message passing algorithms for quantified Boolean formulas (QBF). The first type is a message passing based heuristics that can prove unsatisfiability of the QBF by assigning the universal variables in such a way that the remaining formula is unsatisfiable. In the second type, we use message passing to guide branching heuristics of a Davis-Putnam Logemann-Loveland (DPLL) complete solver. Numerical experiments show that on random QBFs our branching heuristics gives robust exponential efficiency gain with respect to the state-of-art solvers. We also manage to solve some previously unsolved benchmarks from the QBFLIB library. Apart from this our study sheds light on using message passing in small systems and as subroutines in complete solvers.
Segmentation Based Approach to Dynamic Page Construction from Search Engine Results
Venue: arXiv cs.IR 2012
Year: 2012

The results rendered by the search engines are mostly a linear snippet list. With the prolific increase in the dynamism of web pages there is a need for enhanced result lists from search engines in order to cope-up with the expectations of the users. This paper proposes a model for dynamic construction of a resultant page from various results fetched by the search engine, based on the web page segmentation approach. With the incorporation of personalization through user profile during the candidate segment selection, the enriched resultant page is constructed. The benefits of this approach include instant, one-shot navigation to relevant portions from various result items, in contrast to a linear page-by-page visit approach. The experiments conducted on the prototype model with various levels of users, quantifies the improvements in terms of amount of relevant information fetched.
Polymer Expansions for Cycle LDPC Codes
Venue: arXiv cs.IT 2012
Year: 2012

We prove that the Bethe expression for the conditional input-output entropy of cycle LDPC codes on binary symmetric channels above the MAP threshold is exact in the large block length limit. The analysis relies on methods from statistical physics. The finite size corrections to the Bethe expression are expressed through a polymer expansion which is controlled thanks to expander and counting arguments.
An Investigation of the Laws of Traversals
Venue: arXiv cs.PL 2012
Year: 2012

Traversals of data structures are ubiquitous in programming. Consequently, it is important to be able to characterise those structures that are traversable and understand their algebraic properties. Traversable functors have been characterised by McBride and Paterson as those equipped with a distributive law over arbitrary applicative functors; however, laws that fully capture the intuition behind traversals are missing. This article is an attempt to remedy this situation by proposing laws for characterising traversals that capture the intuition behind them. To support our claims, we prove that finitary containers are traversable in our sense and argue that elements in a traversable structure are visited exactly once.
A Formal Comparison of Approaches to Datatype-Generic Programming
Venue: arXiv cs.PL 2012
Year: 2012

Datatype-generic programming increases program abstraction and reuse by making functions operate uniformly across different types. Many approaches to generic programming have been proposed over the years, most of them for Haskell, but recently also for dependently typed languages such as Agda. Different approaches vary in expressiveness, ease of use, and implementation techniques. Some work has been done in comparing the different approaches informally. However, to our knowledge there have been no attempts to formally prove relations between different approaches. We thus present a formal comparison of generic programming libraries. We show how to formalise different approaches in Agda, including a coinductive representation, and then establish theorems that relate the approaches to each other. We provide constructive proofs of inclusion of one approach in another that can be used to convert between approaches, helping to reduce code duplication across different libraries. Our formalisation also helps in providing a clear picture of the potential of each approach, especially in relating different generic views and their expressiveness.
Evaluation strategies for monadic computations
Venue: arXiv cs.PL 2012
Year: 2012

Monads have become a powerful tool for structuring effectful computations in functional programming, because they make the order of effects explicit. When translating pure code to a monadic version, we need to specify evaluation order explicitly. Two standard translations give call-by-value and call-by-name semantics. The resulting programs have different structure and types, which makes revisiting the choice difficult. In this paper, we translate pure code to monadic using an additional operation malias that abstracts out the evaluation strategy. The malias operation is based on computational comonads; we use a categorical framework to specify the laws that are required to hold about the operation. For any monad, we show implementations of malias that give call-by-value and call-by-name semantics. Although we do not give call-by-need semantics for all monads, we show how to turn certain monads into an extended monad with call-by-need semantics, which partly answers an open question. Moreover, using our unified translation, it is possible to change the evaluation strategy of functional code translated to the monadic form without changing its structure or types.
Irrelevance, Heterogeneous Equality, and Call-by-value Dependent Type Systems
Venue: arXiv cs.PL 2012
Year: 2012

We present a full-spectrum dependently typed core language which includes both nontermination and computational irrelevance (a.k.a. erasure), a combination which has not been studied before. The two features interact: to protect type safety we must be careful to only erase terminating expressions. Our language design is strongly influenced by the choice of CBV evaluation, and by our novel treatment of propositional equality which has a heterogeneous, completely erased elimination form.
From Mathematics to Abstract Machine: A formal derivation of an executable Krivine machine
Venue: arXiv cs.PL 2012
Year: 2012

This paper presents the derivation of an executable Krivine abstract machine from a small step interpreter for the simply typed lambda calculus in the dependently typed programming language Agda.
Theoretical Analysis and Tuning of Decentralized Probabilistic Auto-Scaling
Venue: arXiv cs.DC 2012
Year: 2012

A major impediment towards the industrial adoption of decentralized distributed systems comes from the difficulty to theoretically prove that these systems exhibit the required behavior. In this paper, we use probability theory to analyze a decentralized auto-scaling algorithm in which each node probabilistically decides to scale in or out. We prove that, in the context of dynamic workloads, the average load of the system is maintained within a variation interval with a given probability, provided that the number of nodes and the variation interval length are higher than certain bounds. The paper also proposes numerical algorithms for approximating these minimum bounds.
No-reference image quality assessment through the von Mises distribution
Venue: arXiv cs.CV 2012
Year: 2012

An innovative way of calculating the von Mises distribution (VMD) of image entropy is introduced in this paper. The VMD's concentration parameter and some fitness parameter that will be later defined, have been analyzed in the experimental part for determining their suitability as a image quality assessment measure in some particular distortions such as Gaussian blur or additive Gaussian noise. To achieve such measure, the local Rényi entropy is calculated in four equally spaced orientations and used to determine the parameters of the von Mises distribution of the image entropy. Considering contextual images, experimental results after applying this model show that the best-in-focus noise-free images are associated with the highest values for the von Mises distribution concentration parameter and the highest approximation of image data to the von Mises distribution model. Our defined von Misses fitness parameter experimentally appears also as a suitable no-reference image quality assessment indicator for no-contextual images.
Computing Resolution-Path Dependencies in Linear Time
Venue: arXiv cs.DS 2012
Year: 2012

The alternation of existential and universal quantifiers in a quantified boolean formula (QBF) generates dependencies among variables that must be respected when evaluating the formula. Dependency schemes provide a general framework for representing such dependencies. Since it is generally intractable to determine dependencies exactly, a set of potential dependencies is computed instead, which may include false positives. Among the schemes proposed so far, resolution-path dependencies introduce the fewest spurious dependencies. In this work, we describe an algorithm that detects resolution-path dependencies in linear time, resolving a problem posed by Van Gelder (CP 2011).
Scalability of Data Binding in ASP.NET Web Applications
Venue: arXiv cs.DB 2012
Year: 2012

ASP.NET web applications typically employ server controls to provide dynamic web pages, and data-bound server controls to display and maintain database data. Most developers use default properties of ASP.NET server controls when developing web applications, which allows for rapid development of workable applications. However, creating a high-performance, multi-user, and scalable web application requires enhancement of server controls using custom-made code. In this empirical study we evaluate the impact of various technical approaches for paging and sorting functionality in data-driven ASP.NET web applications: automatic data paging and sorting in web server controls on web server; paging and sorting on database server; indexed and non-indexed database columns; clustered vs. non-clustered indices. We observed significant performance improvements when custom paging based on SQL stored procedure and clustered index is used.