OpenRaiser/Intern-Atlas huggingface dataset:
Searching Polyhedra by Rotating Half-Planes
Venue: arXiv cs.CG 2011
Year: 2011

The Searchlight Scheduling Problem was first studied in 2D polygons, where the goal is for point guards in fixed positions to rotate searchlights to catch an evasive intruder. Here the problem is extended to 3D polyhedra, with the guards now boundary segments who rotate half-planes of illumination. After carefully detailing the 3D model, several results are established. The first is a nearly direct extension of the planar one-way sweep strategy using what we call exhaustive guards, a generalization that succeeds despite there being no well-defined notion in 3D of planar "clockwise rotation". Next follow two results: every polyhedron with r>0 reflex edges can be searched by at most r^2 suitably placed guards, whereas just r guards suffice if the polyhedron is orthogonal. (Minimizing the number of guards to search a given polyhedron is easily seen to be NP-hard.) Finally we show that deciding whether a given set of guards has a successful search schedule is strongly NP-hard, and that deciding if a given target area is searchable at all is strongly PSPACE-hard, even for orthogonal polyhedra. A number of peripheral results are proved en route to these central theorems, and several open problems remain for future work.
A Data Mining view on Class Room Teaching Language
Venue: arXiv cs.DB 2011
Year: 2011

From ancient period in India, educational institution embarked to use class room teaching. Where a teacher explains the material and students understand and learn the lesson. There is no absolute scale for measuring knowledge but examination score is one scale which shows the performance indicator of students. So it is important that appropriate material is taught but it is vital that while teaching which language is chosen, class notes must be prepared and attendance. This study analyses the impact of language on the presence of students in class room. The main idea is to find out the support, confidence and interestingness level for appropriate language and attendance in the classroom. For this purpose association rule is used.
MiCi: A Novel Micro-Level Temporal Channel Imploration for Mobile Hosts
Venue: arXiv cs.NI 2011
Year: 2011

The exponential increase of multimedia services by the mobile users requires seamless connectivity with cost effective Quality of Service QoS provisioning. For providing such on-demand QoS, the network needs to utilize the radio channels among the Mobile Hosts (MHs) effectively. We use vector genetic algorithm VGA for temporal imploration of sharable channel(s) from the neighbouring cells to fulfill the needs of a cell. We propose a new micro-level temporal channel imploration mechanism MiCi, which promptly allocates available borrowing channel s of the neighbouring cell(s) to the needy cell. The novelty of MiCi is scalability, high availability, and on demand allocation of the channels to the desired cells. The performance of our model has been tested by simulation against a standard FCA scheme as well as a Greedy Borrowing Heuristic. In all the test cases MiCi shows promising results in comparison to both the schemes.
QoS-Aware Base-Station Selections for Distributed MIMO Links in Broadband Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

We propose the QoS-aware BS-selection schemes for the distributed wireless MIMO links, which aim at minimizing the BS usages and reducing the interfering range, while satisfying diverse statistical delay-QoS constraints characterized by the delay-bound violation probability and the effective capacity technique. In particular, based on the channel state information (CSI) and QoS requirements, a subset of BS with variable cardinality for the distributed MIMO transmission is dynamically selected, where the selections are controlled by a central server. For the single-user scenario, we develop two optimization frameworks, respectively, to derive the efficient BS-selection schemes and the corresponding resource allocation algorithms. One framework uses the incremental BS-selection and time-sharing (IBS-TS) strategies, and the other employs the ordered-gain based BS-selection and probabilistic transmissions (OGBS-PT). The IBS-TS framework can yield better performance, while the scheme developed under the OGBS-PT framework is easier to implement. For the multi-user scenario, we propose the optimization framework applying the priority BS-selection, block-diagonalization precoding, and probabilistic transmission (PBS-BD-PT) techniques. We also propose the optimization framework applying the priority BS-selection, time-division-multiple-access, and probabilistic transmission (PBS-TDMA-PT) techniques. We derive the optimal transmission schemes for all the aforementioned frameworks, respectively. Also conducted is a set of simulation evaluations which compare our proposed schemes with several baseline schemes and show the impact of the delay-QoS requirements, transmit power, and traffic loads on the performances of BS selections for distributed MIMO systems.
Universally Attainable Error and Information Exponents, and Equivocation Rate for the Broadcast Channels with Confidential Messages
Venue: arXiv cs.IT 2011
Year: 2011

We show universally attainable exponents for the decoding error and the mutual information and universally attainable equivocation rates for the conditional entropy for the broadcast channels with confidential messages. The error exponents are the same as ones given by Korner and Sgarro for the broadcast channels with degraded message sets.
Array independent MIMO channel models with analytical characteristics
Venue: arXiv cs.IT 2011
Year: 2011

The conventional analytical channel models for multiple-input multiple-output (MIMO) wireless radio channels are array dependent. In this paper, we present several array independent MIMO channel models that inherit the essence of analytical models. The key idea is to decompose the physical scattering channel into two parts using the manifold decomposition technique: one is the wavefield independent sampling matrices depending on the antenna arrays only; the other is the array independent physical channel that can be individually modeled in an analytical manner. Based on the framework, we firstly extend the conventional virtual channel representation (VCR), which is restricted to uniform linear arrays (ULAs) so far, to a general version applicable to arbitrary array configurations. Then, we present two array independent stochastic MIMO channel models based on the proposed new VCR as well as the Weichselberger model. These two models are good at angular power spectrum (APS) estimation and capacity prediction, respectively. Finally, the impact of array characteristics on channel capacity is separately investigated by studying the condition number of the array steering matrix at fixed angles, and the results agree well with existing conclusions. Numerical results are presented for model validation and comparison.
Convex Approaches to Model Wavelet Sparsity Patterns
Venue: arXiv cs.CV 2011
Year: 2011

Statistical dependencies among wavelet coefficients are commonly represented by graphical models such as hidden Markov trees(HMTs). However, in linear inverse problems such as deconvolution, tomography, and compressed sensing, the presence of a sensing or observation matrix produces a linear mixing of the simple Markovian dependency structure. This leads to reconstruction problems that are non-convex optimizations. Past work has dealt with this issue by resorting to greedy or suboptimal iterative reconstruction methods. In this paper, we propose new modeling approaches based on group-sparsity penalties that leads to convex optimizations that can be solved exactly and efficiently. We show that the methods we develop perform significantly better in deconvolution and compressed sensing applications, while being as computationally efficient as standard coefficient-wise approaches such as lasso.
Testing of random matrices
Venue: arXiv cs.DM 2011
Year: 2011

Let $n$ be a positive integer and $X = [x_{ij}]_{1 \leq i, j \leq n}$ be an $n \times n$\linebreak \noindent sized matrix of independent random variables having joint uniform distribution $$\hbox{Pr} {x_{ij} = k \hbox{for} 1 \leq k \leq n} = \frac{1}{n} \quad (1 \leq i, j \leq n) \koz. $$ A realization $\mathcal{M} = [m_{ij}]$ of $X$ is called \textit{good}, if its each row and each column contains a permutation of the numbers $1, 2,..., n$. We present and analyse four typical algorithms which decide whether a given realization is good.
Phylogeny and geometry of languages from normalized Levenshtein distance
Venue: arXiv cs.CL 2011
Year: 2011

The idea that the distance among pairs of languages can be evaluated from lexical differences seems to have its roots in the work of the French explorer Dumont D'Urville. He collected comparative words lists of various languages during his voyages aboard the Astrolabe from 1826 to 1829 and, in his work about the geographical division of the Pacific, he proposed a method to measure the degree of relation between languages. The method used by the modern lexicostatistics, developed by Morris Swadesh in the 1950s, measures distances from the percentage of shared cognates, which are words with a common historical origin. The weak point of this method is that subjective judgment plays a relevant role. Recently, we have proposed a new automated method which is motivated by the analogy with genetics. The new approach avoids any subjectivity and results can be easily replicated by other scholars. The distance between two languages is defined by considering a renormalized Levenshtein distance between pair of words with the same meaning and averaging on the words contained in a list. The renormalization, which takes into account the length of the words, plays a crucial role, and no sensible results can be found without it. In this paper we give a short review of our automated method and we illustrate it by considering the cluster of Malagasy dialects. We show that it sheds new light on their kinship relation and also that it furnishes a lot of new information concerning the modalities of the settlement of Madagascar.
Opportunistic Wireless Relay Networks: Diversity-Multiplexing Tradeoff
Venue: arXiv cs.IT 2011
Year: 2011

Opportunistic analysis has traditionally relied on independence assumptions that break down in many interesting and useful network topologies. This paper develops techniques that expand opportunistic analysis to a broader class of networks, proposes new opportunistic methods for several network geometries, and analyzes them in the high-SNR regime. For each of the geometries studied in the paper, we analyze the opportunistic DMT of several relay protocols, including amplify-and-forward, decode-and-forward, compress-and-forward, non-orthogonal amplify-forward, and dynamic decode-forward. Among the highlights of the results: in a variety of multi-user single-relay networks, simple selection strategies are developed and shown to be DMT-optimal. It is shown that compress-forward relaying achieves the DMT upper bound in the opportunistic multiple-access relay channel as well as in the opportunistic nxn user network with relay. Other protocols, e.g. dynamic decode-forward, are shown to be near optimal in several cases. Finite-precision feedback is analyzed for the opportunistic multiple-access relay channel, the opportunistic broadcast relay channel, and the opportunistic gateway channel, and is shown to be almost as good as full channel state information.
Performance Analysis of AODV under Black Hole Attack through Use of OPNET Simulator
Venue: arXiv cs.CR 2011
Year: 2011

Mobile ad hoc networks (MANETs) are dynamic wireless networks without any infrastructure. These networks are weak against many types of attacks. One of these attacks is the black hole. In this attack, a malicious node advertises itself as having freshest or shortest path to specific node to absorb packets to itself. The effect of black hole attack on ad hoc network using AODV as a routing protocol will be examined in this research. Furthermore, we investigate solution for increasing security in these networks. Simulation results using OPNET simulator depict that packet delivery ratio in the presence of malicious nodes, reduces notably.
Boolean Equi-propagation for Optimized SAT Encoding
Venue: arXiv cs.AI 2011
Year: 2011

We present an approach to propagation based solving, Boolean equi-propagation, where constraints are modelled as propagators of information about equalities between Boolean literals. Propagation based solving applies this information as a form of partial evaluation resulting in optimized SAT encodings. We demonstrate for a variety of benchmarks that our approach results in smaller CNF encodings and leads to speed-ups in solving times.
Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs
Venue: arXiv cs.DM 2011
Year: 2011

The disjoint convex obstacle number of a graph G is the smallest number h such that there is a set of h pairwise disjoint convex polygons (obstacles) and a set of n points in the plane (corresponding to V(G)) so that a vertex pair uv is an edge if and only if the corresponding segment uv does not meet any obstacle. We show that the disjoint convex obstacle number of an outerplanar graph is always at most 5, and of a bipartite permutation graph at most 4. The former answers a question raised by Alpert, Koch, and Laison. We complement the upper bound for outerplanar graphs with the lower bound of 4.
TripNet: A Method for Constructing Phylogenetic Networks from Triplets
Venue: arXiv cs.CE 2011
Year: 2011

We present TripNet, a method for constructing phylogenetic networks from triplets. We will present the motivations behind our approach and its theoretical and empirical justification. To demonstrate the accuracy and efficiency of TripNet, we performed two simulations and also applied the method to five published data sets: Kreitman's data, a set of triplets from real yeast data obtained from the Fungal Biodiversity Center in Utrecht, a collection of 110 highly recombinant Salmonella multi-locus sequence typing sequences, and nrDNA ITS and cpDNA JSA sequence data of New Zealand alpine buttercups of Ranunculus sect. Pseudadonis. Finally, we compare our results with those already obtained by other authors using alternative methods. TripNet, data sets, and supplementary files are freely available for download at (www.bioinf.cs.ipm.ir/softwares/tripnet).
Data Base Mappings and Theory of Sketches
Venue: arXiv cs.DB 2011
Year: 2011

In this paper we will present the two basic operations for database schemas used in database mapping systems (separation and Data Federation), and we will explain why the functorial semantics for database mappings needed a new base category instead of usual Set category. Successively, it is presented a definition of the graph G for a schema database mapping system, and the definition of its sketch category Sch(G). Based on this framework we presented functorial semantics for database mapping systems with the new base category DB.
3-List Colouring Permutation Graphs
Venue: arXiv cs.DM 2011
Year: 2011

3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation graphs.
Synthesizing Robust Plans under Incomplete Domain Models
Venue: arXiv cs.AI 2011
Year: 2011

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to generate plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness, and formalize the notion of plan robustness with respect to an incomplete domain model. We then propose an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem. We present experimental results with Probabilistic-FF, a state-of-the-art planner, showing the promise of our approach.
Cuckoo Hashing with Pages
Venue: arXiv cs.DS 2011
Year: 2011

Although cuckoo hashing has significant applications in both theoretical and practical settings, a relevant downside is that it requires lookups to multiple locations. In many settings, where lookups are expensive, cuckoo hashing becomes a less compelling alternative. One such standard setting is when memory is arranged in large pages, and a major cost is the number of page accesses. We propose the study of cuckoo hashing with pages, advocating approaches where each key has several possible locations, or cells, on a single page, and additional choices on a second backup page. We show experimentally that with k cell choices on one page and a single backup cell choice, one can achieve nearly the same loads as when each key has k+1 random cells to choose from, with most lookups requiring just one page access, even when keys are placed online using a simple algorithm. While our results are currently experimental, they suggest several interesting new open theoretical questions for cuckoo hashing with pages.
Reducing Fuzzy Answer Set Programming to Model Finding in Fuzzy Logics
Venue: arXiv cs.PL 2011
Year: 2011

In recent years answer set programming has been extended to deal with multi-valued predicates. The resulting formalisms allows for the modeling of continuous problems as elegantly as ASP allows for the modeling of discrete problems, by combining the stable model semantics underlying ASP with fuzzy logics. However, contrary to the case of classical ASP where many efficient solvers have been constructed, to date there is no efficient fuzzy answer set programming solver. A well-known technique for classical ASP consists of translating an ASP program $P$ to a propositional theory whose models exactly correspond to the answer sets of $P$. In this paper, we show how this idea can be extended to fuzzy ASP, paving the way to implement efficient fuzzy ASP solvers that can take advantage of existing fuzzy logic reasoners. To appear in Theory and Practice of Logic Programming (TPLP).
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
Venue: arXiv cs.DS 2011
Year: 2011

A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of εand independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.
Content-Based Spam Filtering on Video Sharing Social Networks
Venue: arXiv cs.CV 2011
Year: 2011

In this work we are concerned with the detection of spam in video sharing social networks. Specifically, we investigate how much visual content-based analysis can aid in detecting spam in videos. This is a very challenging task, because of the high-level semantic concepts involved; of the assorted nature of social networks, preventing the use of constrained a priori information; and, what is paramount, of the context dependent nature of spam. Content filtering for social networks is an increasingly demanded task: due to their popularity, the number of abuses also tends to increase, annoying the user base and disrupting their services. We systematically evaluate several approaches for processing the visual information: using static and dynamic (motionaware) features, with and without considering the context, and with or without latent semantic analysis (LSA). Our experiments show that LSA is helpful, but taking the context into consideration is paramount. The whole scheme shows good results, showing the feasibility of the concept.
VIZGR: Combining Data on a Visual Level
Venue: arXiv cs.HC 2011
Year: 2011

In this paper we present a novel method to connect data on the visualization level. In general, visualizations are a dead end, when it comes to reusability. Yet, users prefer to work with visualizations as evidenced by WYSIWYG editors. To enable users to work with their data in a way that is intuitive to them, we have created Vizgr. Vizgr.com offers basic visualization methods, like graphs, tag clouds, maps and time lines. But unlike normal data visualizations, these can be re-used, connected to each other and to web sites. We offer a simple opportunity to combine diverse data structures, such as geo-locations and networks, with each other by a mouse click. In an evaluation, we found that over 85 % of the participants were able to use and understand this technology without any training or explicit instructions.
Chance-constrained Model Predictive Control for Multi-Agent Systems
Venue: arXiv cs.SY 2011
Year: 2011

We consider stochastic model predictive control of a multi-agent systems with constraints on the probabilities of inter-agent collisions. We first study a sample-based approximation of the collision probabilities and use this approximation to formulate constraints for the stochastic control problem. This approximation will converge as the number of samples goes to infinity, however, the complexity of the resulting control problem is so high that this approach proves unsuitable for control under real-time requirements. To alleviate the computational burden we propose a second approach that uses probabilistic bounds to determine regions with increased probability of presence for each agent and formulate constraints for the control problem that guarantee that these regions will not overlap. We prove that the resulting problem is conservative for the original problem with probabilistic constraints, ie. every control strategy that is feasible under our new constraints will automatically be feasible for the original problem. Furthermore we show in simulations in a UAV path planning scenario that our proposed approach grants significantly better run-time performance compared to a controller with the sample-based approximation with only a small degree of sub-optimality resulting from the conservativeness of our new approach.