OpenRaiser/Intern-Atlas huggingface dataset:
Prize-collecting Network Design on Planar Graphs
Venue: arXiv cs.DS 2010
Year: 2010

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF) and more generally Submodular Prize-Collecting Steiner Forest (SPCSF) on planar graphs (and more generally bounded-genus graphs) to the same problems on graphs of bounded treewidth. More precisely, we show any $α$-approximation algorithm for these problems on graphs of bounded treewidth gives an $(α+ ε)$-approximation algorithm for these problems on planar graphs (and more generally bounded-genus graphs), for any constant $ε> 0$. Since PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth using dynamic programming, we obtain PTASs for these problems on planar graphs and bounded-genus graphs. In contrast, we show PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. This result is interesting on its own because it gives the first provable hardness separation between prize-collecting and non-prize-collecting (regular) versions of the problems: regular Steiner Forest is known to be polynomially solvable on series-parallel graphs and admits a PTAS on graphs of bounded treewidth. An analogous hardness result can be shown for Euclidian PCSF. This ends the common belief that prize-collecting variants should not add any new hardness to the problems.
Formal Derivation of Concurrent Garbage Collectors
Venue: arXiv cs.DC 2010
Year: 2010

Concurrent garbage collectors are notoriously difficult to implement correctly. Previous approaches to the issue of producing correct collectors have mainly been based on posit-and-prove verification or on the application of domain-specific templates and transformations. We show how to derive the upper reaches of a family of concurrent garbage collectors by refinement from a formal specification, emphasizing the application of domain-independent design theories and transformations. A key contribution is an extension to the classical lattice-theoretic fixpoint theorems to account for the dynamics of concurrent mutation and collection.
Receive Diversity and Ergodic Performance of Interference Alignment on the MIMO Gaussian Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

We consider interference alignment (IA) over K-user Gaussian MIMO interference channel (MIMO-IC) when the SNR is not asymptotically high. We introduce a generalization of IA which enables receive diversity inside the interference-free subspace. We generalize the existence criterion of an IA solution proposed by Yetis et al. to this case, thereby establishing a multi-user diversity-multiplexing trade-off (DMT) for the interference channel. Furthermore, we derive a closed-form tight lower-bound for the ergodic mutual information achievable using IA over a Gaussian MIMO-IC with Gaussian i.i.d. channel coefficients at arbitrary SNR, when the transmitted signals are white inside the subspace defined by IA. Finally, as an application of the previous results, we compare the performance achievable by IA at various operating points allowed by the DMT, to a recently introduced distributed method based on game theory.
Fundamental Rate-Reliability-Complexity Limits in Outage Limited MIMO Communications
Venue: arXiv cs.IT 2010
Year: 2010

The work establishes fundamental limits with respect to rate, reliability and computational complexity, for a general setting of outage-limited MIMO communications. In the high-SNR regime, the limits are optimized over all encoders, all decoders, and all complexity regulating policies. The work then proceeds to explicitly identify encoder-decoder designs and policies, that meet this optimal tradeoff. In practice, the limits aim to meaningfully quantify different pertinent measures, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal number of numerical operations (i.e., flops) per bit. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders.
Algorithm and Implementation of the Blog-Post Supervision Process
Venue: arXiv cs.OH 2010
Year: 2010

A web log or blog in short is a trendy way to share personal entries with others through website. A typical blog may consist of texts, images, audios and videos etc. Most of the blogs work as personal online diaries, while others may focus on specific interest such as photographs (photoblog), art (artblog), travel (tourblog), IT (techblog) etc. Another type of blogging called microblogging is also very well known now-a-days which contains very short posts. Like the developed countries, the users of blogs are gradually increasing in the developing countries e.g. Bangladesh. Due to the nature of open access to all users, some people misuse it to spread fake news to achieve individual or political goals. Some of them also post vulgar materials that make an embarrass situation for other bloggers. Even, sometimes it indulges the reputation of the victim. The only way to overcome this problem is to bring all the posts under supervision of the blog moderator. But it totally contradicts with blogging concepts. In this paper, we have implemented an algorithm that would help to prevent the offensive entries from being posted. These entries would go through a supervision process to justify themselves as legal posts. From the analysis of the result, we have shown that this approach can eliminate the chaotic situations in blogosphere at a great extent. Our experiment shows that about 90% of offensive posts can be detected and stopped from being published using this approach.
Human Disease Diagnosis Using a Fuzzy Expert System
Venue: arXiv cs.AI 2010
Year: 2010

Human disease diagnosis is a complicated process and requires high level of expertise. Any attempt of developing a web-based expert system dealing with human disease diagnosis has to overcome various difficulties. This paper describes a project work aiming to develop a web-based fuzzy expert system for diagnosing human diseases. Now a days fuzzy systems are being used successfully in an increasing number of application areas; they use linguistic rules to describe systems. This research project focuses on the research and development of a web-based clinical tool designed to improve the quality of the exchange of health information between health care professionals and patients. Practitioners can also use this web-based tool to corroborate diagnosis. The proposed system is experimented on various scenarios in order to evaluate it's performance. In all the cases, proposed system exhibits satisfactory results.
Gender Based Emotion Recognition System for Telugu Rural Dialects Using Hidden Markov Models
Venue: arXiv cs.OH 2010
Year: 2010

Automatic emotion recognition in speech is a research area with a wide range of applications in human interactions. The basic mathematical tool used for emotion recognition is Pattern recognition which involves three operations, namely, pre-processing, feature extraction and classification. This paper introduces a procedure for emotion recognition using Hidden Markov Models (HMM), which is used to divide five emotional states: anger, surprise, happiness, sadness and neutral state. The approach is based on standard speech recognition technology using hidden continuous markov model by selection of low level features and the design of the recognition system. Emotional Speech Database from Telugu Rural Dialects of Andhra Pradesh (TRDAP) was designed using several speaker's voices comprising the emotional states. The accuracy of recognizing five different emotions for both genders of classification is 80% for anger-emotion which is achieved by using the best combination of 39-dimensioanl feature vector for every frame (13 MFCCs, 13 Delta Coefficients and 13 Acceleration Coefficients) and a classifier using HMM. This outcome very much matches with that acquired with the same database with subjective evaluation by human judges. Both gender-dependent and gender-independent experiments are conducted on TRDAP emotional speech database.
An Efficient Technique for Similarity Identification between Ontologies
Venue: arXiv cs.AI 2010
Year: 2010

Ontologies usually suffer from the semantic heterogeneity when simultaneously used in information sharing, merging, integrating and querying processes. Therefore, the similarity identification between ontologies being used becomes a mandatory task for all these processes to handle the problem of semantic heterogeneity. In this paper, we propose an efficient technique for similarity measurement between two ontologies. The proposed technique identifies all candidate pairs of similar concepts without omitting any similar pair. The proposed technique can be used in different types of operations on ontologies such as merging, mapping and aligning. By analyzing its results a reasonable improvement in terms of completeness, correctness and overall quality of the results has been found.
A Middleware Framework for Constraint-Based Deployment and Autonomic Management of Distributed Applications
Venue: arXiv cs.DC 2010
Year: 2010

We propose a middleware framework for deployment and subsequent autonomic management of component-based distributed applications. An initial deployment goal is specified using a declarative constraint language, expressing constraints over aspects such as component-host mappings and component interconnection topology. A constraint solver is used to find a configuration that satisfies the goal, and the configuration is deployed automatically. The deployed application is instrumented to allow subsequent autonomic management. If, during execution, the manager detects that the original goal is no longer being met, the satisfy/deploy process can be repeated automatically in order to generate a revised deployment that does meet the goal.
Stability (over time) of Modified-CS and LS-CS for Recursive Causal Sparse Reconstruction
Venue: arXiv cs.IT 2010
Year: 2010

In this work, we obtain sufficient conditions for the ``stability" of our recently proposed algorithms, modified-CS (for noisy measurements) and Least Squares CS-residual (LS-CS), designed for recursive reconstruction of sparse signal sequences from noisy measurements. By ``stability" we mean that the number of misses from the current support estimate and the number of extras in it remain bounded by a time-invariant value at all times. The concept is meaningful only if the bound is small compared to the current signal support size. A direct corollary is that the reconstruction errors are also bounded by a time-invariant and small value.
Decentralized Fair Scheduling in Two-Hop Relay-Assisted Cognitive OFDMA Systems
Venue: arXiv cs.PF 2010
Year: 2010

In this paper, we consider a two-hop relay-assisted cognitive downlink OFDMA system (named as secondary system) dynamically accessing a spectrum licensed to a primary network, thereby improving the efficiency of spectrum usage. A cluster-based relay-assisted architecture is proposed for the secondary system, where relay stations are employed for minimizing the interference to the users in the primary network and achieving fairness for cell-edge users. Based on this architecture, an asymptotically optimal solution is derived for jointly controlling data rates, transmission power, and subchannel allocation to optimize the average weighted sum goodput where the proportional fair scheduling (PFS) is included as a special case. This solution supports decentralized implementation, requires small communication overhead, and is robust against imperfect channel state information at the transmitter (CSIT) and sensing measurement. The proposed solution achieves significant throughput gains and better user-fairness compared with the existing designs. Finally, we derived a simple and asymptotically optimal scheduling solution as well as the associated closed-form performance under the proportional fair scheduling for a large number of users. The system throughput is shown to be $\mathcal{O}\left(N(1-q_p)(1-q_p^N)\ln\ln K_c\right)$, where $K_c$ is the number of users in one cluster, $N$ is the number of subchannels and $q_p$ is the active probability of primary users.
Open-Ended Evolutionary Robotics: an Information Theoretic Approach
Venue: arXiv cs.RO 2010
Year: 2010

This paper is concerned with designing self-driven fitness functions for Embedded Evolutionary Robotics. The proposed approach considers the entropy of the sensori-motor stream generated by the robot controller. This entropy is computed using unsupervised learning; its maximization, achieved by an on-board evolutionary algorithm, implements a "curiosity instinct", favouring controllers visiting many diverse sensori-motor states (sms). Further, the set of sms discovered by an individual can be transmitted to its offspring, making a cultural evolution mode possible. Cumulative entropy (computed from ancestors and current individual visits to the sms) defines another self-driven fitness; its optimization implements a "discovery instinct", as it favours controllers visiting new or rare sensori-motor states. Empirical results on the benchmark problems proposed by Lehman and Stanley (2008) comparatively demonstrate the merits of the approach.
The comparison of Wiktionary thesauri transformed into the machine-readable format
Venue: arXiv cs.IR 2010
Year: 2010

Wiktionary is a unique, peculiar, valuable and original resource for natural language processing (NLP). The paper describes an open-source Wiktionary parser: its architecture and requirements followed by a description of Wiktionary features to be taken into account, some open problems of Wiktionary and the parser. The current implementation of the parser extracts the definitions, semantic relations, and translations from English and Russian Wiktionaries. The paper's goal is to interest researchers (1) in using the constructed machine-readable dictionary for different NLP tasks, (2) in extending the software to parse 170 still unused Wiktionaries. The comparison of a number and types of semantic relations, a number of definitions, and a number of translations in the English Wiktionary and the Russian Wiktionary has been carried out. It was found that the number of semantic relations in the English Wiktionary is larger by 1.57 times than in Russian (157 and 100 thousands). But the Russian Wiktionary has more "rich" entries (with a big number of semantic relations), e.g. the number of entries with three or more semantic relations is larger by 1.63 times than in the English Wiktionary. Upon comparison, it was found out the methodological shortcomings of the Wiktionary.
An expectation transformer approach to predicate abstraction and data independence for probabilistic programs
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we revisit the well-known technique of predicate abstraction to characterise performance attributes of system models incorporating probability. We recast the theory using expectation transformers, and identify transformer properties which correspond to abstractions that yield nevertheless exact bound on the performance of infinite state probabilistic systems. In addition, we extend the developed technique to the special case of "data independent" programs incorporating probability. Finally, we demonstrate the subtleness of the extended technique by using the PRISM model checking tool to analyse an infinite state protocol, obtaining exact bounds on its performance.
A new tool for the performance analysis of massively parallel computer systems
Venue: arXiv cs.PF 2010
Year: 2010

We present a new tool, GPA, that can generate key performance measures for very large systems. Based on solving systems of ordinary differential equations (ODEs), this method of performance analysis is far more scalable than stochastic simulation. The GPA tool is the first to produce higher moment analysis from differential equation approximation, which is essential, in many cases, to obtain an accurate performance prediction. We identify so-called switch points as the source of error in the ODE approximation. We investigate the switch point behaviour in several large models and observe that as the scale of the model is increased, in general the ODE performance prediction improves in accuracy. In the case of the variance measure, we are able to justify theoretically that in the limit of model scale, the ODE approximation can be expected to tend to the actual variance of the model.
The Link Prediction Problem in Bipartite Networks
Venue: arXiv cs.LG 2010
Year: 2010

We define and study the link prediction problem in bipartite networks, specializing general link prediction algorithms to the bipartite case. In a graph, a link prediction function of two vertices denotes the similarity or proximity of the vertices. Common link prediction functions for general graphs are defined using paths of length two between two nodes. Since in a bipartite graph adjacency vertices can only be connected by paths of odd lengths, these functions do not apply to bipartite graphs. Instead, a certain class of graph kernels (spectral transformation kernels) can be generalized to bipartite graphs when the positive-semidefinite kernel constraint is relaxed. This generalization is realized by the odd component of the underlying spectral transformation. This construction leads to several new link prediction pseudokernels such as the matrix hyperbolic sine, which we examine for rating graphs, authorship graphs, folksonomies, document--feature networks and other types of bipartite networks.
From Encounters to Plausible Mobility
Venue: arXiv cs.NI 2010
Year: 2010

Inferring plausible node mobility based only on information from wireless contact traces is a difficult problem. Working with mobility information allows richer protocol simulations, particularly in dense networks, but requires complex set-ups to measure. On the other hand, contact information is easier to measure but only allows for simplistic simulation models. In a contact trace a lot of node movement information is irretrievably lost so the original positions and velocities are in general out of reach. In this paper, we propose a fast heuristic algorithm, inspired by dynamic force-based graph drawing, capable of inferring a plausible movement from any contact trace, and evaluate it on both synthetic and real-life contact traces. Our results reveal that (i) the quality of the inferred mobility is directly linked to the precision of the measured contact trace, and (ii) the simple addition of appropriate anticipation forces between nodes leads to an accurate inferred mobility.
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time
Venue: arXiv cs.DS 2010
Year: 2010

The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $n\ge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Θ(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Ω(n)$.
Better algorithms for satisfiability problems for formulas of bounded rank-width
Venue: arXiv cs.DM 2010
Year: 2010

We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known -- e.g.~[Fischer, Makowsky, and Ravve] -- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.
Fatigue evaluation in maintenance and assembly operations by digital human simulation
Venue: arXiv cs.RO 2010
Year: 2010

Virtual human techniques have been used a lot in industrial design in order to consider human factors and ergonomics as early as possible. The physical status (the physical capacity of virtual human) has been mostly treated as invariable in the current available human simulation tools, while indeed the physical capacity varies along time in an operation and the change of the physical capacity depends on the history of the work as well. Virtual Human Status is proposed in this paper in order to assess the difficulty of manual handling operations, especially from the physical perspective. The decrease of the physical capacity before and after an operation is used as an index to indicate the work difficulty. The reduction of physical strength is simulated in a theoretical approach on the basis of a fatigue model in which fatigue resistances of different muscle groups were regressed from 24 existing maximum endurance time (MET) models. A framework based on digital human modeling technique is established to realize the comparison of physical status. An assembly case in airplane assembly is simulated and analyzed under the framework. The endurance time and the decrease of the joint moment strengths are simulated. The experimental result in simulated operations under laboratory conditions confirms the feasibility of the theoretical approach.
Counterexample Guided Abstraction Refinement Algorithm for Propositional Circumscription
Venue: arXiv cs.AI 2010
Year: 2010

Circumscription is a representative example of a nonmonotonic reasoning inference technique. Circumscription has often been studied for first order theories, but its propositional version has also been the subject of extensive research, having been shown equivalent to extended closed world assumption (ECWA). Moreover, entailment in propositional circumscription is a well-known example of a decision problem in the second level of the polynomial hierarchy. This paper proposes a new Boolean Satisfiability (SAT)-based algorithm for entailment in propositional circumscription that explores the relationship of propositional circumscription to minimal models. The new algorithm is inspired by ideas commonly used in SAT-based model checking, namely counterexample guided abstraction refinement. In addition, the new algorithm is refined to compute the theory closure for generalized close world assumption (GCWA). Experimental results show that the new algorithm can solve problem instances that other solutions are unable to solve.
Secret key agreement on wiretap channels with transmitter side information
Venue: arXiv cs.IT 2010
Year: 2010

Secret-key agreement protocols over wiretap channels controlled by a state parameter are studied. The entire state sequence is known (non-causally) to the sender but not to the receiver and the eavesdropper. Upper and lower bounds on the secret-key capacity are established both with and without public discussion. The proposed coding scheme involves constructing a codebook to create common reconstruction of the state sequence at the sender and the receiver and another secret-key codebook constructed by random binning. For the special case of Gaussian channels, with no public discussion, - the secret-key generation with dirty paper problem, the gap between our bounds is at-most 1/2 bit and the bounds coincide in the high signal-to-noise ratio and high interference-to-noise ratio regimes. In the presence of public discussion our bounds coincide, yielding the capacity, when then the channels of the receiver and the eavesdropper satisfy an in- dependent noise condition.