OpenRaiser/Intern-Atlas huggingface dataset:
Task Assignment in Tree-Like Hierarchical Structures
Venue: arXiv cs.DS 2014
Year: 2014

Most large organizations, such as corporations, are hierarchical organizations. In hierarchical organizations each entity in the organization, except the root entity, is a sub-part of another entity. In this paper we study the task assignment problem to the entities of tree-like hierarchical organizations. The inherent tree structure introduces an interesting and challenging constraint to the standard assignment problem. When a task is assigned to an entity in a hierarchical organization, the whole entity, including its sub-entities, is responsible from the execution of that particular task. In other words, if an entity has been assigned to a task, neither its descendants nor its ancestors can be assigned to a task. Sub-entities cannot be assigned as they have an ancestor already occupied. Ancestor entities cannot be assigned since one of their sub-entities has already been employed in an assignment. In the paper, we formally introduce this new version of the assignment problem called Maximum Weight Tree Matching ($MWTM$), and show its NP-hardness. We also propose an effective heuristic solution based on an iterative LP-relaxation to it.
Threesomes, Degenerates, and Love Triangles
Venue: arXiv cs.DS 2014
Year: 2014

The 3SUM problem is to decide, given a set of $n$ real numbers, whether any three sum to zero. It is widely conjectured that a trivial $O(n^2)$-time algorithm is optimal and over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies $Ω(n^2)$ lower bounds on numerous problems in computational geometry and a variant of the conjecture implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this paper we refute the 3SUM conjecture. We prove that the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$ and give two subquadratic 3SUM algorithms, a deterministic one running in $O(n^2 / (\log n/\log\log n)^{2/3})$ time and a randomized one running in $O(n^2 (\log\log n)^2 / \log n)$ time with high probability. Our results lead directly to improved bounds for $k$-variate linear degeneracy testing for all odd $k\ge 3$. The problem is to decide, given a linear function $f(x_1,\ldots,x_k) = α_0 + \sum_{1\le i\le k} α_i x_i$ and a set $A \subset \mathbb{R}$, whether $0\in f(A^k)$. We show the decision tree complexity of this problem is $O(n^{k/2}\sqrt{\log n})$. Finally, we give a subcubic algorithm for a generalization of the $(\min,+)$-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in weighted graphs. We give a depth-$O(n^{5/2}\sqrt{\log n})$ decision tree for this problem, as well as an algorithm running in time $O(n^3 (\log\log n)^2/\log n)$.
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
Venue: arXiv cs.DS 2014
Year: 2014

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$, or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{O(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{O(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$, or: * finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; * finds an isomorphism-invariant construction term --- an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width $O(k^4)$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal.
Games for the Strategic Influence of Expectations
Venue: arXiv cs.GT 2014
Year: 2014

We introduce a new class of games where each player's aim is to randomise her strategic choices in order to affect the other players' expectations aside from her own. The way each player intends to exert this influence is expressed through a Boolean combination of polynomial equalities and inequalities with rational coefficients. We offer a logical representation of these games as well as a computational study of the existence of equilibria.
Execution Time Analysis for Industrial Control Applications
Venue: arXiv cs.SE 2014
Year: 2014

Estimating the execution time of software components is often mandatory when evaluating the non-functional properties of software-intensive systems. This particularly holds for real-time embedded systems, e.g., in the context of industrial automation. In practice it is however very hard to obtain reliable execution time estimates which are accurate, but not overly pessimistic with respect to the typical behavior of the software. This article proposes two new concepts to ease the use of execution time analysis for industrial control applications: (1) a method based on recurring occurrences of code sequences for automatically creating a timing model of a given processor and (2) an interactive way to integrate execution time analysis into the development environment, thus making timing analysis results easily accessible for software developers. The proposed methods are validated by an industrial case study, which shows that a significant amount of code reuse is present in a set of representative industrial control applications.
Transformation of UML Behavioral Diagrams to Support Software Model Checking
Venue: arXiv cs.SE 2014
Year: 2014

Unified Modeling Language (UML) is currently accepted as the standard for modeling (object-oriented) software, and its use is increasing in the aerospace industry. Verification and Validation of complex software developed according to UML is not trivial due to complexity of the software itself, and the several different UML models/diagrams that can be used to model behavior and structure of the software. This paper presents an approach to transform up to three different UML behavioral diagrams (sequence, behavioral state machines, and activity) into a single Transition System to support Model Checking of software developed in accordance with UML. In our approach, properties are formalized based on use case descriptions. The transformation is done for the NuSMV model checker, but we see the possibility in using other model checkers, such as SPIN. The main contribution of our work is the transformation of a non-formal language (UML) to a formal language (language of the NuSMV model checker) towards a greater adoption in practice of formal methods in software development.
Generalized Signal Alignment For Arbitrary MIMO Two-Way Relay Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the arbitrary MIMO two-way relay channels, where there are $K$ source nodes, each equipped with $M_i$ antennas, for $i=1,2,\cdots,K$, and one relay node, equipped with $N$ antennas. Each source node can exchange independent messages with arbitrary other source nodes assisted by the relay. We extend our newly-proposed transmission scheme, generalized signal alignment (GSA) in [1], to arbitrary MIMO two-way relay channels when $N>M_i+M_j$, $\forall i \neq j$. The key idea of GSA is to cancel the interference for each data pair in its specific subspace by two steps. This is realized by jointly designing the precoding matrices at all source nodes and the processing matrix at the relay node. Moreover, the aligned subspaces are orthogonal to each other. By applying the GSA, we show that a necessary condition on the antenna configuration to achieve the DoF upper bound $\min \{\sum_{i=1}^K M_i, 2\sum_{i=2}^K M_i,2N\}$ is $N \geq \max\{\sum_{i=1}^K M_i-M_s-M_t+d_{s,t}\mid \forall s,t\}$. Here, $d_{s,t}$ denotes the DoF of the message exchanged between source node $s$ and $t$. In the special case when the arbitrary MIMO two-way relay channel reduces to the $K$-user MIMO Y channel, we show that our achievable region of DoF upper bound is larger than the previous work.
A Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem
Venue: arXiv cs.NE 2014
Year: 2014

The 0-1 knapsack problem is a well-known combinatorial optimisation problem. Approximation algorithms have been designed for solving it and they return provably good solutions within polynomial time. On the other hand, genetic algorithms are well suited for solving the knapsack problem and they find reasonably good solutions quickly. A naturally arising question is whether genetic algorithms are able to find solutions as good as approximation algorithms do. This paper presents a novel multi-objective optimisation genetic algorithm for solving the 0-1 knapsack problem. Experiment results show that the new algorithm outperforms its rivals, the greedy algorithm, mixed strategy genetic algorithm, and greedy algorithm + mixed strategy genetic algorithm.
The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes
Venue: arXiv cs.DS 2014
Year: 2014

Previous work identifying depth-optimal $n$-channel sorting networks for $9\leq n \leq 16$ is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until $n=40$.
Expressiveness via Intensionality and Concurrency
Venue: arXiv cs.LO 2014
Year: 2014

Computation can be considered by taking into account two dimensions: extensional versus intensional, and sequential versus concurrent. Traditionally sequential extensional computation can be captured by the lambda-calculus. However, recent work shows that there are more expressive intensional calculi such as SF-calculus. Traditionally process calculi capture computation by encoding the lambda-calculus, such as in the pi-calculus. Following this increased expressiveness via intensionality, other recent work has shown that concurrent pattern calculus is more expressive than pi-calculus. This paper formalises the relative expressiveness of all four of these calculi by placing them on a square whose edges are irreversible encodings. This square is representative of a more general result: that expressiveness increases with both intensionality and concurrency.
A Class of Reducible Cyclic Codes and Their Weight Distribution
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a family of reducible cyclic codes over GF(p) whose duals have four zeros is presented, where p is an odd prime. Furthermore, the weight distribution of these cyclic codes is determined.
New Julia and Mandelbrot Sets for Jungck Ishikawa Iterates
Venue: arXiv cs.GR 2014
Year: 2014

The generation of fractals and study of the dynamics of polynomials is one of the emerging and interesting field of research nowadays. We introduce in this paper the dynamics of polynomials z^ n - z + c = 0 for n>=2 and applied Jungck Ishikawa Iteration to generate new Relative Superior Mandelbrot sets and Relative Superior Julia sets. In order to solve this function by Jungck type iterative schemes, we write it in the form of Sz = Tz, where the function T, S are defined as Tz = z^ n + c and Sz = z. Only mathematical explanations are derived by applying Jungck Ishikawa Iteration for polynomials in the literature but in this paper we have generated Relative Mandelbrot sets and Relative Julia sets.
A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting
Venue: arXiv cs.CC 2014
Year: 2014

We devise a new pseudorandom generator against degree 2 polynomial threshold functions in the Gaussian setting. We manage to achieve $ε$ error with seed length polylogarithmic in $ε$ and the dimension, and exponential improvement over previous constructions.
Performance of Multiantenna Linear MMSE Receivers in Doubly Stochastic Networks
Venue: arXiv cs.IT 2014
Year: 2014

A technique is presented to characterize the Signal-to-Interference-plus-Noise Ratio (SINR) of a representative link with a multiantenna linear Minimum-Mean-Square-Error receiver in a wireless network with transmitting nodes distributed according to a doubly stochastic process, which is a generalization of the Poisson point process. The cumulative distribution function of the SINR of the representative link is derived assuming independent Rayleigh fading between antennas. Several representative spatial node distributions are considered, including networks with both deterministic and random clusters, strip networks (used to model roadways, e.g.), hard-core networks and networks with generalized path-loss models. In addition, it is shown that if the number of antennas at the representative receiver is increased linearly with the nominal node density, the signal-to-interference ratio converges in distribution to a random variable that is non-zero in general, and a positive constant in certain cases. This result indicates that to the extent that the system assumptions hold, it is possible to scale such networks by increasing the number of receiver antennas linearly with the node density. The results presented here are useful in characterizing the performance of multiantenna wireless networks in more general network models than what is currently available.
Duration-Differentiated Services in Electricity
Venue: arXiv cs.SY 2014
Year: 2014

The integration of renewable sources poses challenges at the operational and economic levels of the power grid. In terms of keeping the balance between supply and demand, the usual scheme of supply following load may not be appropriate for large penetration levels of uncertain and intermittent renewable supply. In this paper, we focus on an alternative scheme in which the load follows the supply, exploiting the flexibility associated with the demand side. We consider a model of flexible loads that are to be serviced by zero-marginal cost renewable power together with conventional generation if necessary. Each load demands 1 kW for a specified number of time slots within an operational period. The flexibility of a load resides in the fact that the service may be delivered over any slots within the operational period. Loads therefore require flexible energy services that are differentiated by the demanded duration. We focus on two problems associated with durations-differentiated loads. The first problem deals with the operational decisions that a supplier has to make to serve a given set of duration differentiated loads. The second problem focuses on a market implementation for duration differentiated services. We give necessary and sufficient conditions under which the available power can service the loads, and we describe an algorithm that constructs an appropriate allocation. In the event the available supply is inadequate, we characterize the minimum amount of power that must be purchased to service the loads. Next we consider a forward market where consumers can purchase duration differentiated energy services. We first characterize social welfare maximizing allocations in this forward market and then show the existence of an efficient competitive equilibrium.
Persistence based analysis of consensus protocols for dynamic graph networks
Venue: arXiv cs.SY 2014
Year: 2014

This article deals with the consensus problem involving agents with time-varying singularities in the dynamics or communication in undirected graph networks. Existing results provide control laws which guarantee asymptotic consensus. These results are based on the analysis of a system switching between piecewise constant and time-invariant dynamics. This work introduces a new analysis technique relying upon classical notions of persistence of excitation to study the convergence properties of the time-varying multi-agent dynamics. Since the individual edge weights pass through singularities and vary with time, the closed-loop dynamics consists of a non-autonomous linear system. Instead of simplifying to a piecewise continuous switched system as in literature, smooth variations in edge weights are allowed, albeit assuming an underlying persistence condition which characterizes sufficient inter-agent communication to reach consensus. The consensus task is converted to edge-agreement in order to study a stabilization problem to which classical persistence based results apply. The new technique allows precise computation of the rate of convergence to the consensus value.
Coalgebraic Weak Bisimulation from Recursive Equations over Monads
Venue: arXiv cs.LO 2014
Year: 2014

Strong bisimulation for labelled transition systems is one of the most fundamental equivalences in process algebra, and has been generalised to numerous classes of systems that exhibit richer transition behaviour. Nearly all of the ensuing notions are instances of the more general notion of coalgebraic bisimulation. Weak bisimulation, however, has so far been much less amenable to a coalgebraic treatment. Here we attempt to close this gap by giving a coalgebraic treatment of (parametrized) weak equivalences, including weak bisimulation. Our analysis requires that the functor defining the transition type of the system is based on a suitable order-enriched monad, which allows us to capture weak equivalences by least fixpoints of recursive equations. Our notion is in agreement with existing notions of weak bisimulations for labelled transition systems, probabilistic and weighted systems, and simple Segala systems.
Detecting criminal organizations in mobile phone networks
Venue: arXiv cs.SI 2014
Year: 2014

The study of criminal networks using traces from heterogeneous communication media is acquiring increasing importance in nowadays society. The usage of communication media such as phone calls and online social networks leaves digital traces in the form of metadata that can be used for this type of analysis. The goal of this work is twofold: first we provide a theoretical framework for the problem of detecting and characterizing criminal organizations in networks reconstructed from phone call records. Then, we introduce an expert system to support law enforcement agencies in the task of unveiling the underlying structure of criminal networks hidden in communication data. This platform allows for statistical network analysis, community detection and visual exploration of mobile phone network data. It allows forensic investigators to deeply understand hierarchies within criminal organizations, discovering members who play central role and provide connection among sub-groups. Our work concludes illustrating the adoption of our computational framework for a real-word criminal investigation.
Optimizing Relay Precoding for Wireless Coordinated Relaying
Venue: arXiv cs.IT 2014
Year: 2014

Processing of multiple communication flows in wireless systems has given rise to a number of novel transmission techniques, notably the two-way relaying based on wireless network coding. Recently, a related set of techniques has emerged, termed coordinated direct and relay (CDR) transmissions, where the constellation of traffic flows is more general than the two-way. Regardless of the actual traffic flows, in a CDR scheme the relay has a central role in managing the interference and boosting the overall system performance. In this paper we investigate the novel transmission modes, based on amplify-and-forward, that arise when the relay is equipped with multiple antennas and can use beamforming.
Design of a High Speed FPGA-Based Classifier for Efficient Packet Classification
Venue: arXiv cs.NI 2014
Year: 2014

Packet classification is a vital and complicated task as the processing of packets should be done at a specified line speed. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. Hence the matching of packets should be much faster and simpler for quick processing and classification. A hardware accelerator or a classifier has been proposed here using a modified version of the HyperCuts packet classification algorithm. A new pre-cutting process has been implemented to reduce the memory size to fit in an FPGA. This classifier can classify packets with high speed and with a power consumption factor of less than 3W. This methodology removes the need for floating point division to be performed by replacing the region compaction scheme of HyperCuts by pre-cutting, while classifying the packets and concentrates on classifying the packets at the core of the network.
Model Predictive Control (MPC) Applied To Coupled Tank Liquid Level System
Venue: arXiv cs.SY 2014
Year: 2014

Coupled Tank system used for liquid level control is a model of plant that has usually been used in industries especially chemical process industries. Level control is also very important for mixing reactant process. This survey paper tries to presents in a systemic way an approach predictive control strategy for a system that is similar to the process and is represented by two liquid tanks. This system of coupled Tank is one of the most commonly available systems representing a coupled Multiple Input Multiple Output (MIMO) system. With 2 inputs and 2 outputs, it is the most primitive form of a coupled multivariable system. Therefor the basic concept of how the coupled tanks system works is by using a numerical system which it operates with a flow control valve FCV as main control of the level of liquid in one tank or both tanks. For this paper, MPC algorithm control is used which will be developed below. And it is focuses on the design and modelling for coupled tanks system. The steps followed for the design of the controller are: Developing a state space system model for the coupled tank system then design an MPC controller for the developed system model. And study the effect of the disturbance on measured level output. Note that the implementation Model Predictive Controller on flow controller valve in a Coupled Tank liquid level system is one of the new methods of controlling liquid level.
A Compression Technique for Analyzing Disagreement-Based Active Learning
Venue: arXiv cs.LG 2014
Year: 2014

We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.
Text Based Approach For Indexing And Retrieval Of Image And Video: A Review
Venue: arXiv cs.IR 2014
Year: 2014

Text data present in multimedia contain useful information for automatic annotation, indexing. Extracted information used for recognition of the overlay or scene text from a given video or image. The Extracted text can be used for retrieving the videos and images. In this paper, firstly, we are discussed the different techniques for text extraction from images and videos. Secondly, we are reviewed the techniques for indexing and retrieval of image and videos by using extracted text.