OpenRaiser/Intern-Atlas huggingface dataset:
Robust optimization with incremental recourse
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we consider an adaptive approach to address optimization problems with uncertain cost parameters. Here, the decision maker selects an initial decision, observes the realization of the uncertain cost parameters, and then is permitted to modify the initial decision. We treat the uncertainty using the framework of robust optimization in which uncertain parameters lie within a given set. The decision maker optimizes so as to develop the best cost guarantee in terms of the worst-case analysis. The recourse decision is ``incremental"; that is, the decision maker is permitted to change the initial solution by a small fixed amount. We refer to the resulting problem as the robust incremental problem. We study robust incremental variants of several optimization problems. We show that the robust incremental counterpart of a linear program is itself a linear program if the uncertainty set is polyhedral. Hence, it is solvable in polynomial time. We establish the NP-hardness for robust incremental linear programming for the case of a discrete uncertainty set. We show that the robust incremental shortest path problem is NP-complete when costs are chosen from a polyhedral uncertainty set, even in the case that only one new arc may be added to the initial path. We also address the complexity of several special cases of the robust incremental shortest path problem and the robust incremental minimum spanning tree problem.
EGuaranteeNash for Boolean Games is NEXP-Hard
Venue: arXiv cs.GT 2013
Year: 2013

Boolean games are an expressive and natural formalism through which to investigate problems of strategic interaction in multiagent systems. Although they have been widely studied, almost all previous work on Nash equilibria in Boolean games has focused on the restricted setting of pure strategies. This is a shortcoming as finite games are guaranteed to have at least one equilibrium in mixed strategies, but many simple games fail to have pure strategy equilibria at all. We address this by showing that a natural decision problem about mixed equilibria: determining whether a Boolean game has a mixed strategy equilibrium that guarantees every player a given payoff, is NEXP-hard. Accordingly, the $ε$ variety of the problem is NEXP-complete. The proof can be adapted to show coNEXP-hardness of a similar question: whether all Nash equilibria of a Boolean game guarantee every player at least the given payoff.
Aperiodic tilings and entropy
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we present a construction of Kari-Culik aperiodic tile set - the smallest known until now. With the help of this construction, we prove that this tileset has positive entropy. We also explain why this result was not expected.
Parallel Firewalls on General-Purpose Graphics Processing Units
Venue: arXiv cs.DC 2013
Year: 2013

Firewalls use a rule database to decide which packets will be allowed from one network onto another thereby implementing a security policy. In high-speed networks as the inter-arrival rate of packets decreases, the latency incurred by a firewall increases. In such a scenario, a single firewall become a bottleneck and reduces the overall throughput of the network.A firewall with heavy load, which is supposed to be a first line of defense against attacks, becomes susceptible to Denial of Service (DoS) attacks. Many works are being done to optimize firewalls.This paper presents our implementation of different parallel firewall models on General-Purpose Graphics Processing Unit (GPGPU). We implemented the parallel firewall architecture proposed in and introduced a new model that can effectively exploit the massively parallel computing capabilities of GPGPU.
Three New Families of Zero-difference Balanced Functions with Applications
Venue: arXiv cs.IT 2013
Year: 2013

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction, inspired by the recent work \cite{Cai13}, gives ZDB functions defined on the abelian groups $(\gf(q_1) \times \cdots \times \gf(q_k), +)$ with new and flexible parameters. The other two constructions are based on $2$-cyclotomic cosets and yield ZDB functions on $\Z_n$ with new parameters. The parameters of optimal constant composition codes, optimal and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized.
Strategic Argumentation is NP-Complete
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we study the complexity of strategic argumentation for dialogue games. A dialogue game is a 2-player game where the parties play arguments. We show how to model dialogue games in a skeptical, non-monotonic formalism, and we show that the problem of deciding what move (set of rules) to play at each turn is an NP-complete problem.
Probabilistic Programming Concepts
Venue: arXiv cs.PL 2013
Year: 2013

A multitude of different probabilistic programming languages exists today, all extending a traditional programming language with primitives to support modeling of complex, structured probability distributions. Each of these languages employs its own probabilistic primitives, and comes with a particular syntax, semantics and inference procedure. This makes it hard to understand the underlying programming concepts and appreciate the differences between the different languages. To obtain a better understanding of probabilistic programming, we identify a number of core programming concepts underlying the primitives used by various probabilistic languages, discuss the execution mechanisms that they require and use these to position state-of-the-art probabilistic languages and their implementation. While doing so, we focus on probabilistic extensions of logic programming languages such as Prolog, which have been developed since more than 20 years.
Abstraction in decision-makers with limited information processing capabilities
Venue: arXiv cs.AI 2013
Year: 2013

A distinctive property of human and animal intelligence is the ability to form abstractions by neglecting irrelevant information which allows to separate structure from noise. From an information theoretic point of view abstractions are desirable because they allow for very efficient information processing. In artificial systems abstractions are often implemented through computationally costly formations of groups or clusters. In this work we establish the relation between the free-energy framework for decision making and rate-distortion theory and demonstrate how the application of rate-distortion for decision-making leads to the emergence of abstractions. We argue that abstractions are induced due to a limit in information processing capacity.
Rectifying Self Organizing Maps for Automatic Concept Learning from Web Images
Venue: arXiv cs.CV 2013
Year: 2013

We attack the problem of learning concepts automatically from noisy web image search results. Going beyond low level attributes, such as colour and texture, we explore weakly-labelled datasets for the learning of higher level concepts, such as scene categories. The idea is based on discovering common characteristics shared among subsets of images by posing a method that is able to organise the data while eliminating irrelevant instances. We propose a novel clustering and outlier detection method, namely Rectifying Self Organizing Maps (RSOM). Given an image collection returned for a concept query, RSOM provides clusters pruned from outliers. Each cluster is used to train a model representing a different characteristics of the concept. The proposed method outperforms the state-of-the-art studies on the task of learning low-level concepts, and it is competitive in learning higher level concepts as well. It is capable to work at large scale with no supervision through exploiting the available sources.
A distributed prime sieving algorithm based on Scheduling by Multiple Edge Reversal
Venue: arXiv cs.DC 2013
Year: 2013

This paper presents a new distributed approach for generating all prime numbers in a given interval of integers. From Eratosthenes, who elaborated the first prime sieve (more than 2000 years ago), to the current generation of parallel computers, which have permitted to reach larger bounds on the interval or to obtain previous results in a shorter time, prime numbers generation still represents an attractive domain of research and plays a central role in cryptography. We propose a fully distributed algorithm for finding all primes in the interval $[2\ldots, n]$, based on the \emph{wheel sieve} and the SMER (\emph{Scheduling by Multiple Edge Reversal}) multigraph dynamics. Given a multigraph $\mathcal{M}$ of arbitrary topology, having $N$ nodes, a SMER-driven system is defined by the number of directed edges (arcs) between any two nodes of $\mathcal{M}$, and by the global period length of all "arc reversals" in $\mathcal{M}$. The new prime number generation method inherits the distributed and parallel nature of SMER and requires at most $n + \lfloor \sqrt{n}\rfloor$ time steps. The message complexity achieves at most $nΔ_N + \lfloor \sqrt{n}\rfloor Δ_N$, where $1\le Δ_N\le N - 1$ is the maximal multidegree of $\mathcal{M}$, and the maximal amount of memory space required per process is $\mathcal{O}(n)$ bits.
Probable convexity and its application to Correlated Topic Models
Venue: arXiv cs.LG 2013
Year: 2013

Non-convex optimization problems often arise from probabilistic modeling, such as estimation of posterior distributions. Non-convexity makes the problems intractable, and poses various obstacles for us to design efficient algorithms. In this work, we attack non-convexity by first introducing the concept of \emph{probable convexity} for analyzing convexity of real functions in practice. We then use the new concept to analyze an inference problem in the \emph{Correlated Topic Model} (CTM) and related nonconjugate models. Contrary to the existing belief of intractability, we show that this inference problem is concave under certain conditions. One consequence of our analyses is a novel algorithm for learning CTM which is significantly more scalable and qualitative than existing methods. Finally, we highlight that stochastic gradient algorithms might be a practical choice to resolve efficiently non-convex problems. This finding might find beneficial in many contexts which are beyond probabilistic modeling.
Intelligent Bug Algorithm (IBA): A Novel Strategy to Navigate Mobile Robots Autonomously
Venue: arXiv cs.RO 2013
Year: 2013

This research proposed an intelligent obstacle avoidance algorithm to navigate an autonomous mobile robot. The presented Intelligent Bug Algorithm (IBA) over performs and reaches the goal in relatively less time as compared to existing Bug algorithms. The improved algorithm offers a goal oriented strategy by following smooth and short trajectory. This has been achieved by continuously considering the goal position during obstacle avoidance. The proposed algorithm is computationally inexpensive and easy to tune. The paper also presents the performance comparison of IBA and reported Bug algorithms. Simulation results of robot navigation in an environment with obstacles demonstrate the performance of the improved algorithm.
FFTPL: An Analytic Placement Algorithm Using Fast Fourier Transform for Density Equalization
Venue: arXiv cs.CE 2013
Year: 2013

We propose a flat nonlinear placement algorithm FFTPL using fast Fourier transform for density equalization. The placement instance is modeled as an electrostatic system with the analogy of density cost to the potential energy. A well-defined Poisson's equation is proposed for gradient and cost computation. Our placer outperforms state-of-the-art placers with better solution quality and efficiency.
Implementation of WSN which can simultaneously monitor Temperature conditions and control robot for positional accuracy
Venue: arXiv cs.RO 2013
Year: 2013

Sensor networks and robots are both quickly evolving fields, the union of two fields seems inherently symbiotic. Collecting data from stationary sensors can be time consuming task and thus can be automated by adding wireless communication capabilities to the sensors. This proposed project takes advantage of wireless sensor networks in remote handling environment which can send signals over far distances by using a mesh topology, transfers the data wirelessly and also consumes low power. In this paper a testbed is created for wireless sensor network using custom build sensor nodes for temperature monitoring in labs and to control a robot moving in another lab. The two temperature sensor nodes used here consists of a Arduino microcontroller and XBee wireless communication module based on IEEE 802.15.4 standard while the robot has inherent FPGA board as a processing unit with xbee module connected via Rs-2332 cable for serial communication between zigbee device and FPGA. A simple custom packet is designed so that uniformity is maintained while collection of data from temperature nodes and a moving robot and passing to a remote terminal. The coordinator Zigbee is connected to remote terminal (PC) through its USB port where Graphical user interface (GUI) can be run to monitor Temperature readings and position of Robot dynamically and save those readings in database.
Une méthode pour caractériser les communautés des réseaux dynamiques à attributs
Venue: arXiv cs.SI 2013
Year: 2013

Many complex systems are modeled through complex networks whose analysis reveals typical topological properties. Amongst those, the community structure is one of the most studied. Many methods are proposed to detect communities, not only in plain, but also in attributed, directed or even dynamic networks. A community structure takes the form of a partition of the node set, which must then be characterized relatively to the properties of the studied system. We propose a method to support such a characterization task. We define a sequence-based representation of networks, combining temporal information, topological measures, and nodal attributes. We then characterize communities using the most representative emerging sequential patterns of its nodes. This also allows detecting unusual behavior in a community. We describe an empirical study of a network of scientific collaborations.---De nombreux systèmes complexes sont étudiés via l'analyse de réseaux dits complexes ayant des propriétés topologiques typiques. Parmi cellesci, les structures de communautés sont particulièrement étudiées. De nombreuses méthodes permettent de les détecter, y compris dans des réseaux contenant des attributs nodaux, des liens orientés ou évoluant dans le temps. La détection prend la forme d'une partition de l'ensemble des noeuds, qu'il faut ensuite caractériser relativement au système modélisé. Nous travaillons sur l'assistance à cette tâche de caractérisation. Nous proposons une représentation des réseaux sous la forme de séquences de descripteurs de noeuds, qui combinent les informations temporelles, les mesures topologiques, et les valeurs des attributs nodaux. Les communautés sont caractérisées au moyen des motifs séquentiels émergents les plus représentatifs issus de leurs noeuds. Ceci permet notamment la détection de comportements inhabituels au sein d'une communauté. Nous décrivons une étude empirique sur un réseau de collaboration scientifique.
The Multiple Instances of Node Centrality and their Implications on the Vulnerability of ISP Networks
Venue: arXiv cs.SI 2013
Year: 2013

The position of the nodes within a network topology largely determines the level of their involvement in various networking functions. Yet numerous node centrality indices, proposed to quantify how central individual nodes are in this respect, yield very different views of their relative significance. Our first contribution in this paper is then an exhaustive survey and categorization of centrality indices along several attributes including the type of information (local vs. global) and processing complexity required for their computation. We next study the seven most popular of those indices in the context of Internet vulnerability to address issues that remain under-explored in literature so far. First, we carry out a correlation study to assess the consistency of the node rankings those indices generate over ISP router-level topologies. For each pair of indices, we compute the full ranking correlation, which is the standard choice in literature, and the percentage overlap between the k top nodes. Then, we let these rankings guide the removal of highly central nodes and assess the impact on both the connectivity properties and traffic-carrying capacity of the network. Our results confirm that the top-k overlap predicts the comparative impact of indices on the network vulnerability better than the full-ranking correlation. Importantly, the locally computed degree centrality index approximates closely the global indices with the most dramatic impact on the traffic-carrying capacity; whereas, its approximative power in terms of connectivity is more topology-dependent.
Software Process Commonality Analysis
Venue: arXiv cs.SE 2013
Year: 2013

To remain viable and thrive, software organizations must rapidly adapt to frequent, and often rather far-ranging, changes to their operational context. These changes typically concern many factors, including the nature of the organization's marketplace in general, its customers' demands, and its business needs. In today's most highly dynamic contexts, such as web services development, other changes create additional, severe challenges. Most critical are changes to the technology in which a software product is written or which the software product has to control or use to provide its functionality. These product-support technology changes are frequently relatively 'small' and incremental. They are, therefore, often handled by relatively 'small,' incremental changes to the organization's software processes. However, the frequency of these changes is high, and their impact is elevated by time-to-market and requirements change demands. The net result is an extremely challenging need to create and manage a large number of customized process variants, collectively having more commonalities than differences, and incorporating experience-based, proven 'best practices'. This paper describes a tool-based approach to coping with product-support technology changes. The approach utilizes established capabilities such as descriptive process modeling and the creation of reference models. It incorporates a new, innovative, tool-based capability to analyze commonalities and differences among processes. The paper includes an example-based evaluation of the approach in the domain of Wireless Internet Services as well as a discussion of its potentially broader application.
Reasoning about the Impacts of Information Sharing
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we describe a decision process framework allowing an agent to decide what information it should reveal to its neighbours within a communication graph in order to maximise its utility. We assume that these neighbours can pass information onto others within the graph. The inferences made by agents receiving the messages can have a positive or negative impact on the information providing agent, and our decision process seeks to identify how a message should be modified in order to be most beneficial to the information producer. Our decision process is based on the provider's subjective beliefs about others in the system, and therefore makes extensive use of the notion of trust. Our core contributions are therefore the construction of a model of information propagation; the description of the agent's decision procedure; and an analysis of some of its properties.
Predictive Monitoring of Business Processes
Venue: arXiv cs.SE 2013
Year: 2013

Modern information systems that support complex business processes generally maintain significant amounts of process execution data, particularly records of events corresponding to the execution of activities (event logs). In this paper, we present an approach to analyze such event logs in order to predictively monitor business goals during business process execution. At any point during an execution of a process, the user can define business goals in the form of linear temporal logic rules. When an activity is being executed, the framework identifies input data values that are more (or less) likely to lead to the achievement of each business goal. Unlike reactive compliance monitoring approaches that detect violations only after they have occurred, our predictive monitoring approach provides early advice so that users can steer ongoing process executions towards the achievement of business goals. In other words, violations are predicted (and potentially prevented) rather than merely detected. The approach has been implemented in the ProM process mining toolset and validated on a real-life log pertaining to the treatment of cancer patients in a large hospital.
Integer-ambiguity resolution in astronomy and geodesy
Venue: arXiv cs.DM 2013
Year: 2013

Recent theoretical developments in astronomical aperture synthesis have revealed the existence of integer-ambiguity problems. Those problems, which appear in the self-calibration procedures of radio imaging, have been shown to be similar to the nearest-lattice point (NLP) problems encountered in high-precision geodetic positioning, and in global navigation satellite systems. In this paper, we analyse the theoretical aspects of the matter and propose new methods for solving those NLP problems. The related optimization aspects concern both the preconditioning stage, and the discrete-search stage in which the integer ambiguities are finally fixed. Our algorithms, which are described in an explicit manner, can easily be implemented. They lead to substantial gains in the processing time of both stages. Their efficiency was shown via intensive numerical tests.
Rainbow path and color degree in edge colored graphs
Venue: arXiv cs.DM 2013
Year: 2013

Let $G$ be an edge colored graph. A {\it}{rainbow path} in $G$ is a path in which all the edges are colored with distinct colors. Let $d^c(v)$ be the color degree of a vertex $v$ in $G$, i.e. the number of distinct colors present on the edges incident on the vertex $v$. Let $t$ be the maximum length of a rainbow path in $G$. Chen and Li showed that if $d^c \geq k$, for every vertex $v$ of $G$, then $t \geq \left \lceil \frac{3 k}{5}\right \rceil + 1$ (Long heterochromatic paths in edge-colored graphs, The Electronic Journal of Combinatorics 12 (2005), # R33, Pages:1-33.) Unfortunately, proof by Chen and Li is very long and comes to about 23 pages in the journal version. Chen and Li states in their paper that it was conjectured by Akira Saito, that $t \ge \left \lceil \frac {2k} {3} \right \rceil$. They also states in their paper that they believe $t \ge k - c$ for some constant $c$. In this note, we give a short proof to show that $t \ge \left \lceil \frac{3 k}{5}\right \rceil$, using an entirely different method. Our proof is only about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by Saito and/or Chen and Li.
Semantic Jira - Semantic Expert Finder in the Bug Tracking Tool Jira
Venue: arXiv cs.SE 2013
Year: 2013

The semantic expert recommender extension for the Jira bug tracking system semantically searches for similar tickets in Jira and recommends experts and links to existing organizational (Wiki) knowledge for each ticket. This helps to avoid redundant work and supports the search and collaboration with experts in the project management and maintenance phase based on semantically enriched tickets in Jira.