OpenRaiser/Intern-Atlas huggingface dataset:
Restricted Parameter Range Promise Set Cover Problems Are Easy
Venue: arXiv cs.CC 2011
Year: 2011

Let $({\bf U},{\bf S},d)$ be an instance of Set Cover Problem, where ${\bf U}=\{u_1,...,u_n\}$ is a $n$ element ground set, ${\bf S}=\{S_1,...,S_m\}$ is a set of $m$ subsets of ${\bf U}$ satisfying $\bigcup_{i=1}^m S_i={\bf U}$ and $d$ is a positive integer. In STOC 1993 M. Bellare, S. Goldwasser, C. Lund and A. Russell proved the NP-hardness to distinguish the following two cases of ${\bf GapSetCover_η}$ for any constant $η> 1$. The Yes case is the instance for which there is an exact cover of size $d$ and the No case is the instance for which any cover of ${\bf U}$ from ${\bf S}$ has size at least $ηd$. This was improved by R. Raz and S. Safra in STOC 1997 about the NP-hardness for ${\bf GapSetCover}_{clogm}$ for some constant $c$. In this paper we prove that restricted parameter range subproblem is easy. For any given function of $n$ satisfying $η(n) \geq 1$, we give a polynomial time algorithm not depending on $η(n)$ to distinguish between {\bf YES:} The instance $({\bf U},{\bf S}, d)$ where $d>\frac{2 |{\bf S}|}{3η(n)-1}$, for which there exists an exact cover of size at most $d$; {\bf NO:} The instance $({\bf U},{\bf S}, d)$ where $d>\frac{2 |{\bf S}|}{3η(n)-1}$, for which any cover from ${\bf S}$ has size larger than $η(n) d$. The polynomial time reduction of this restricted parameter range set cover problem is constructed by using the lattice.
Statistical Mechanical Analysis of Low-Density Parity-Check Codes on General Markov Channel
Venue: arXiv cs.IT 2011
Year: 2011

Low-density parity-check (LDPC) codes on symmetric memoryless channels have been analyzed using statistical physics by several authors. In this paper, statistical mechanical analysis of LDPC codes is performed for asymmetric memoryless channels and general Markov channels. It is shown that the saddle point equations of the replica symmetric solution for a Markov channel is equivalent to the density evolution of the belief propagation on the factor graph representing LDPC codes on the Markov channel. The derivation uses the method of types for Markov chain.
The evaluation of geometric queries: constraint databases and quantifier elimination
Venue: arXiv cs.DB 2011
Year: 2011

We model the algorithmic task of geometric elimination (e.g., quantifier elimination in the elementary field theories of real and complex numbers) by means of certain constraint database queries, called geometric queries. As a particular case of such a geometric elimination task, we consider sample point queries. We show exponential lower complexity bounds for evaluating geometric queries in the general and in the particular case of sample point queries. Although this paper is of theoretical nature, its aim is to explore the possibilities and (complexity-)limits of computer implemented query evaluation algorithms for Constraint Databases, based on the principles of the most advanced geometric elimination procedures and their implementations, like, e.g., the software package "Kronecker".
Modelling Mixed Discrete-Continuous Domains for Planning
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we present pddl+, a planning domain description language for modelling mixed discrete-continuous planning domains. We describe the syntax and modelling style of pddl+, showing that the language makes convenient the modelling of complex time-dependent effects. We provide a formal semantics for pddl+ by mapping planning instances into constructs of hybrid automata. Using the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of pddl+ planning instances. An advantage of building a mapping from pddl+ to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities. One consequence is that we can expect to make use of some of the theoretical properties of HAs. For example, for a restricted class of HAs the Reachability problem (which is equivalent to Plan Existence) is decidable. pddl+ provides an alternative to the continuous durative action model of pddl2.1, adding a more flexible and robust model of time-dependent behaviour.
Set Intersection and Consistency in Constraint Networks
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency. This generalizes row convex constraints. Various consistency results are also obtained on constraint networks where only some, in contrast to all in the existing work,constraints are tight.
Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems
Venue: arXiv cs.AI 2011
Year: 2011

Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.
NP Animacy Identification for Anaphora Resolution
Venue: arXiv cs.CL 2011
Year: 2011

In anaphora resolution for English, animacy identification can play an integral role in the application of agreement restrictions between pronouns and candidates, and as a result, can improve the accuracy of anaphora resolution systems. In this paper, two methods for animacy identification are proposed and evaluated using intrinsic and extrinsic measures. The first method is a rule-based one which uses information about the unique beginners in WordNet to classify NPs on the basis of their animacy. The second method relies on a machine learning algorithm which exploits a WordNet enriched with animacy information for each sense. The effect of word sense disambiguation on the two methods is also assessed. The intrinsic evaluation reveals that the machine learning method reaches human levels of performance. The extrinsic evaluation demonstrates that animacy identification can be beneficial in anaphora resolution, especially in the cases where animate entities are identified with high precision.
The complexity of small universal Turing machines: a survey
Venue: arXiv cs.CC 2011
Year: 2011

We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing machines. We finish the survey with results on generalised and restricted Turing machine models including machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and machines that never write to their tape. We then discuss some ideas for future work.
Asymptotic Methods of ODEs: Exploring Singularities of the Second Kind
Venue: arXiv cs.SC 2011
Year: 2011

We develop symbolic methods of asymptotic approximations for solutions of linear ordinary differential equations and use to them stabilize numerical calculations. Our method follows classical analysis for first-order systems and higher-order scalar equations where growth behavior is expressed in terms of elementary functions. We then recast our equations in mollified form - thereby obtaining stability.
Noise Analysis and Detection Based on RF Energy Duration in wireless LAN
Venue: arXiv cs.NI 2011
Year: 2011

Noise is the major problem while working with wireless LAN. In this paper we analyze the noise by using active receiving antenna and also propose the detection mechanism based on RF energy duration. The standard back off mechanism of 802.11 wireless LAN (WLAN) increases the contention window when a transmission failure occurs in order to alleviate contentions in a WLAN. In addition, many proposed schemes for 802.11 WLAN behave adaptively to transmission failures. Transmission failures in WLANs occur mostly by two causes: collision and channel noise. However, in 802.11 WLAN, a station cannot know the cause of a transmission failure, thus the adaptive schemes assume the ideal situation in which all transmission failures occur by only one of two causes. For this reason, they may behave erroneously in a real world where transmission failures occur by both causes. In this paper, we propose a novel scheme to detect collision, which utilizes transmission time information and RF energy duration on the channel. By detecting collisions, a station can differentiate the causes of transmission failures and the adaptive schemes can operate correctly by using the detection information.
Semantic Technology to Exploit Digital Content Exposed as Linked Data
Venue: arXiv cs.DL 2011
Year: 2011

The paper illustrates the research result of the application of semantic technology to ease the use and reuse of digital contents exposed as Linked Data on the web. It focuses on the specific issue of explorative research for the resource selection: a context dependent semantic similarity assessment is proposed in order to compare datasets annotated through terminologies exposed as Linked Data (e.g. habitats, species). Semantic similarity is shown as a building block technology to sift linked data resources. From semantic similarity application, we derived a set of recommendations underlying open issues in scaling the similarity assessment up to the Web of Data.
Countering Gattaca: Efficient and Secure Testing of Fully-Sequenced Human Genomes (Full Version)
Venue: arXiv cs.CR 2011
Year: 2011

Recent advances in DNA sequencing technologies have put ubiquitous availability of fully sequenced human genomes within reach. It is no longer hard to imagine the day when everyone will have the means to obtain and store one's own DNA sequence. Widespread and affordable availability of fully sequenced genomes immediately opens up important opportunities in a number of health-related fields. In particular, common genomic applications and tests performed in vitro today will soon be conducted computationally, using digitized genomes. New applications will be developed as genome-enabled medicine becomes increasingly preventive and personalized. However, this progress also prompts significant privacy challenges associated with potential loss, theft, or misuse of genomic data. In this paper, we begin to address genomic privacy by focusing on three important applications: Paternity Tests, Personalized Medicine, and Genetic Compatibility Tests. After carefully analyzing these applications and their privacy requirements, we propose a set of efficient techniques based on private set operations. This allows us to implement in in silico some operations that are currently performed via in vitro methods, in a secure fashion. Experimental results demonstrate that proposed techniques are both feasible and practical today.
Mixing Board Versus Mouse Interaction In Value Adjustment Tasks
Venue: arXiv cs.HC 2011
Year: 2011

We present a controlled, quantitative study with 12 participants comparing interaction with a haptically enhanced mixing board against interaction with a mouse in an abstract task that is motivated by several practical parameter space exploration settings. The study participants received 24 sets of one to eight integer values between 0 and 127, which they had to match by making adjustments with physical or graphical sliders. Based on recorded slider motion path data, we developed an analysis algorithm that identifies and measures different types of activity intervals, including error time moving irrelevant sliders and end time in breaks after completing each trial item. Our results showed a significant increase in speed of the mixing board interaction accompanied by reduced perceived cognitive load when compared with the traditional mouse-based GUI interaction. The gains in speed are largely due to the improved times required for the hand to reach for the first slider (acquisition time) and also when moving between different ones, while the actual time spent manipulating relevant sliders is very similar for either input device. These results agree strongly with qualitative predictions from Fitts' Law that the larger targets afforded by the mixer handles contributed to its faster performance. For further investigation, we computed a measure of motion simultaneity based on velocity correlation, which allowed to identify types of items for which increased simultaneous adjustments occur. For continuous parameter space exploration our findings suggest that mixing boards are a good option to provide detailed multi-value control. The strengths of this input method particularly show in settings where screen space is precious and undisrupted visual focus is crucial.
Rigorous Calculation of the Partition Function for the Finite Number of Ising Spins
Venue: arXiv cs.DC 2011
Year: 2011

The high-performance scalable parallel algorithm for rigorous calculation of partition function of lattice systems with finite number Ising spins was developed. The parallel calculations run by C++ code with using of Message Passing Interface and massive parallel instructions. The algorithm can be used for the research of the interacting spin systems in the Ising models of 2D and 3D. The processing power and scalability is analyzed for different parallel and distributed systems. Different methods of the speed up measuring allow obtain the super-linear speeding up for the small number of processes. Program code could be useful also for research by exact method of different Ising spin systems, e.g. system with competition interactions.
Issues,Challenges and Tools of Clustering Algorithms
Venue: arXiv cs.IR 2011
Year: 2011

Clustering is an unsupervised technique of Data Mining. It means grouping similar objects together and separating the dissimilar ones. Each object in the data set is assigned a class label in the clustering process using a distance measure. This paper has captured the problems that are faced in real when clustering algorithms are implemented .It also considers the most extensively used tools which are readily available and support functions which ease the programming. Once algorithms have been implemented, they also need to be tested for its validity. There exist several validation indexes for testing the performance and accuracy which have also been discussed here.
Combining Spatial and Temporal Logics: Expressiveness vs. Complexity
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the propositional temporal logic PTL, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The obtained results give a clear picture of the trade-off between expressiveness and computational realisability within the hierarchy. We demonstrate how different combining principles as well as spatial and temporal primitives can produce NP-, PSPACE-, EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics out of components that are at most NP- or PSPACE-complete.
An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events
Venue: arXiv cs.AI 2011
Year: 2011

The treatment of exogenous events in planning is practically important in many real-world domains where the preconditions of certain plan actions are affected by such events. In this paper we focus on planning in temporal domains with exogenous events that happen at known times, imposing the constraint that certain actions in the plan must be executed during some predefined time windows. When actions have durations, handling such temporal constraints adds an extra difficulty to planning. We propose an approach to planning in these domains which integrates constraint-based temporal reasoning into a graph-based planning framework using local search. Our techniques are implemented in a planner that took part in the 4th International Planning Competition (IPC-4). A statistical analysis of the results of IPC-4 demonstrates the effectiveness of our approach in terms of both CPU-time and plan quality. Additional experiments show the good performance of the temporal reasoning techniques integrated into our planner.
PDDL 2.1: Representation vs. Computation
Venue: arXiv cs.AI 2011
Year: 2011

I comment on the PDDL 2.1 language and its use in the planning competition, focusing on the choices made for accommodating time and concurrency. I also discuss some methodological issues that have to do with the move toward more expressive planning languages and the balance needed in planning research between semantics and computation.
Auctions with Severely Bounded Communication
Venue: arXiv cs.GT 2011
Year: 2011

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.
Anytime Heuristic Search
Venue: arXiv cs.AI 2011
Year: 2011

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
ARBAC Policy for a Large Multi-National Bank
Venue: arXiv cs.CR 2011
Year: 2011

Administrative role-based access control (ARBAC) is the first comprehensive administrative model proposed for role-based access control (RBAC). ARBAC has several features for designing highly expressive policies, but current work has not highlighted the utility of these expressive policies. In this report, we present a case study of designing an ARBAC policy for a bank comprising 18 branches. Using this case study we provide an assessment about the features of ARBAC that are likely to be used in realistic policies.
Towards Representation and Validation of Knowledge in Students' Learning Pathway Using Variability Modeling Technique
Venue: arXiv cs.CY 2011
Year: 2011

Nowadays, E-learning system is considered as one of the main pillars in the learning system. Mainly, E-Learning system is designed to serve different types of students. Thus, providing different learning pathways are a must. In this paper, we introduce the variability technique to represent the knowledge in E-learning system. This representation provides different learning pathways which supports the students' diversity. Moreover, we validate the selection of learning pathway by introducing First Order Logic (FOL) rules. Keywords Learning Pathway ; Variability and knowledge representation ; IJCSI
String Matching with Variable Length Gaps
Venue: arXiv cs.DS 2011
Year: 2011

We consider string matching with variable length gaps. Given a string $T$ and a pattern $P$ consisting of strings separated by variable length gaps (arbitrary strings of length in a specified range), the problem is to find all ending positions of substrings in $T$ that match $P$. This problem is a basic primitive in computational biology applications. Let $m$ and $n$ be the lengths of $P$ and $T$, respectively, and let $k$ be the number of strings in $P$. We present a new algorithm achieving time $O(n\log k + m +α)$ and space $O(m + A)$, where $A$ is the sum of the lower bounds of the lengths of the gaps in $P$ and $α$ is the total number of occurrences of the strings in $P$ within $T$. Compared to the previous results this bound essentially achieves the best known time and space complexities simultaneously. Consequently, our algorithm obtains the best known bounds for almost all combinations of $m$, $n$, $k$, $A$, and $α$. Our algorithm is surprisingly simple and straightforward to implement. We also present algorithms for finding and encoding the positions of all strings in $P$ for every match of the pattern.