OpenRaiser/Intern-Atlas huggingface dataset:
Price of Anarchy of Innovation Diffusion in Social Networks
Venue: arXiv cs.GT 2014
Year: 2014

There have been great efforts in studying the cascading behavior in social networks such as the innovation diffusion, etc. Game theoretically, in a social network where individuals choose from two strategies: A (the innovation) and B (the status quo) and get payoff from their neighbors for coordination, it has long been known that the Price of Anarchy (PoA) of this game is not 1, since the Nash equilibrium (NE) where all players take B (B Nash) is inferior to the one all players taking A (A Nash). However, no quantitative analysis has been performed to give an accurate upper bound of PoA in this game. In this paper, we adopt a widely used networked coordination game setting [3] to study how bad a Nash equilibrium can be and give a tight upper bound of the PoA of such games. We show that there is an NE that is slightly worse than the B Nash. On the other hand, the PoA is bounded and the worst NE cannot be much worse than the B Nash. In addition, we discuss how the PoA upper bound would change when compatibility between A and B is introduced, and show an intuitive result that the upper bound strictly decreases as the compatibility is increased.
From Quantum Query Complexity to State Complexity
Venue: arXiv cs.CC 2014
Year: 2014

State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.
Analysis of Timed and Long-Run Objectives for Markov Automata
Venue: arXiv cs.LO 2014
Year: 2014

Markov automata (MAs) extend labelled transition systems with random delays and probabilistic branching. Action-labelled transitions are instantaneous and yield a distribution over states, whereas timed transitions impose a random delay governed by an exponential distribution. MAs are thus a nondeterministic variation of continuous-time Markov chains. MAs are compositional and are used to provide a semantics for engineering frameworks such as (dynamic) fault trees, (generalised) stochastic Petri nets, and the Architecture Analysis & Design Language (AADL). This paper considers the quantitative analysis of MAs. We consider three objectives: expected time, long-run average, and timed (interval) reachability. Expected time objectives focus on determining the minimal (or maximal) expected time to reach a set of states. Long-run objectives determine the fraction of time to be in a set of states when considering an infinite time horizon. Timed reachability objectives are about computing the probability to reach a set of states within a given time interval. This paper presents the foundations and details of the algorithms and their correctness proofs. We report on several case studies conducted using a prototypical tool implementation of the algorithms, driven by the MAPA modelling language for efficiently generating MAs.
Text Classification Using Association Rules, Dependency Pruning and Hyperonymization
Venue: arXiv cs.IR 2014
Year: 2014

We present new methods for pruning and enhancing item- sets for text classification via association rule mining. Pruning methods are based on dependency syntax and enhancing methods are based on replacing words by their hyperonyms of various orders. We discuss the impact of these methods, compared to pruning based on tfidf rank of words.
A Numerical Optimization Algorithm Inspired by the Strawberry Plant
Venue: arXiv cs.NE 2014
Year: 2014

This paper proposes a new numerical optimization algorithm inspired by the strawberry plant for solving complicated engineering problems. Plants like strawberry develop both runners and roots for propagation and search for water resources and minerals. In these plants, runners and roots can be thought of as tools for global and local searches, respectively. The proposed algorithm has three main differences with the trivial nature-inspired optimization algorithms: duplication-elimination of the computational agents at all iterations, subjecting all agents to both small and large movements from the beginning to end, and the lack of communication (information exchange) between agents. Moreover, it has the advantage of using only three parameters to be tuned by user. This algorithm is applied to standard test functions and the results are compared with GA and PSO. The proposed algorithm is also used to solve an open problem in the field of robust control theory. These simulations show that the proposed algorithm can very effectively solve complicated optimization problems.
Induced matchings in graphs of degree at most 4
Venue: arXiv cs.DM 2014
Year: 2014

We show that if $G$ is a connected graph of maximum degree at most $4$, which is not $C_{2,5}$, then the strong matching number of $G$ is at least $\frac{1}{9}n(G)$. This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.
A Survey on Two Dimensional Cellular Automata and Its Application in Image Processing
Venue: arXiv cs.CV 2014
Year: 2014

Parallel algorithms for solving any image processing task is a highly demanded approach in the modern world. Cellular Automata (CA) are the most common and simple models of parallel computation. So, CA has been successfully used in the domain of image processing for the last couple of years. This paper provides a survey of available literatures of some methodologies employed by different researchers to utilize the cellular automata for solving some important problems of image processing. The survey includes some important image processing tasks such as rotation, zooming, translation, segmentation, edge detection, compression and noise reduction of images. Finally, the experimental results of some methodologies are presented.
Impact of video quality and wireless network interface on power consumption of mobile devices
Venue: arXiv cs.MM 2014
Year: 2014

During the last years, many improvements were made to the hardware capability of mobile devices. As mobile software also became more interactive and data processing intensive, the increased power demand could not be compensated by the improvements on battery technology. Adaptive systems can help to balance the demand of applications with the limitations of battery resources. For effective systems, the influence of multimedia quality on power consumption of the components of mobile devices needs to be better understood. In this paper, we analyze the impact of video quality and wireless network type on the energy consumption of a mobile device. We have found that the additional power consumption is up to 38% higher when a movie is played over a WiFi network instead from internal memory and 64% higher in case of a mobile network (3G). We have also discovered that a higher movie quality not only affects the power consumption of the CPU but also the power consumption of the WiFi unit by up to 58% and up to 72% respectively on mobile networks.
Going for Speed: Sublinear Algorithms for Dense r-CSPs
Venue: arXiv cs.DS 2014
Year: 2014

We give new sublinear and parallel algorithms for the extensively studied problem of approximating n-variable r-CSPs (constraint satisfaction problems with constraints of arity r up to an additive error. The running time of our algorithms is O(n/ε^2) + 2^O(1/ε^2) for Boolean r-CSPs and O(k^4 n / ε^2) + 2^O(log k / ε^2) for r-CSPs with constraints on variables over an alphabet of size k. For any constant k this gives optimal dependence on n in the running time unconditionally, while the exponent in the dependence on 1/εis polynomially close to the lower bound under the exponential-time hypothesis, which is 2^Ω(ε^(-1/2)). For Max-Cut this gives an exponential improvement in dependence on 1/εcompared to the sublinear algorithms of Goldreich, Goldwasser and Ron (JACM'98) and a linear speedup in n compared to the algorithms of Mathieu and Schudy (SODA'08). For the maximization version of k-Correlation Clustering problem our running time is O(k^4 n / ε^2) + k^O(1/ε^2), improving the previously best n k^{O(1/ε^3 log k/ε) by Guruswami and Giotis (SODA'06).
How Auto-Encoders Could Provide Credit Assignment in Deep Networks via Target Propagation
Venue: arXiv cs.LG 2014
Year: 2014

We propose to exploit {\em reconstruction} as a layer-local training signal for deep learning. Reconstructions can be propagated in a form of target propagation playing a role similar to back-propagation but helping to reduce the reliance on derivatives in order to perform credit assignment across many levels of possibly strong non-linearities (which is difficult for back-propagation). A regularized auto-encoder tends produce a reconstruction that is a more likely version of its input, i.e., a small move in the direction of higher likelihood. By generalizing gradients, target propagation may also allow to train deep networks with discrete hidden units. If the auto-encoder takes both a representation of input and target (or of any side information) in input, then its reconstruction of input representation provides a target towards a representation that is more likely, conditioned on all the side information. A deep auto-encoder decoding path generalizes gradient propagation in a learned way that can could thus handle not just infinitesimal changes but larger, discrete changes, hopefully allowing credit assignment through a long chain of non-linear operations. In addition to each layer being a good auto-encoder, the encoder also learns to please the upper layers by transforming the data into a space where it is easier to model by them, flattening manifolds and disentangling factors. The motivations and theoretical justifications for this approach are laid down in this paper, along with conjectures that will have to be verified either mathematically or experimentally, including a hypothesis stating that such auto-encoder mediated target propagation could play in brains the role of credit assignment through many non-linear, noisy and discrete transformations.
Graph Transformation Planning via Abstraction
Venue: arXiv cs.AI 2014
Year: 2014

Modern software systems increasingly incorporate self-* behavior to adapt to changes in the environment at runtime. Such adaptations often involve reconfiguring the software architecture of the system. Many systems also need to manage their architecture themselves, i.e., they need a planning component to autonomously decide which reconfigurations to execute to reach a desired target configuration. For the specification of reconfigurations, we employ graph transformations systems (GTS) due to the close relation of graphs and UML object diagrams. We solve the resulting planning problems with a planning system that works directly on a GTS. It features a domain-independent heuristic that uses the solution length of an abstraction of the original problem as an estimate. Finally, we provide experimental results on two different domains, which confirm that our heuristic performs better than another domain-independent heuristic which resembles heuristics employed in related work.
Backwards State-space Reduction for Planning in Dynamic Knowledge Bases
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we address the problem of planning in rich domains, where knowledge representation is a key aspect for managing the complexity and size of the planning domain. We follow the approach of Description Logic (DL) based Dynamic Knowledge Bases, where a state of the world is represented concisely by a (possibly changing) ABox and a (fixed) TBox containing the axioms, and actions that allow to change the content of the ABox. The plan goal is given in terms of satisfaction of a DL query. In this paper we start from a traditional forward planning algorithm and we propose a much more efficient variant by combining backward and forward search. In particular, we propose a Backward State-space Reduction technique that consists in two phases: first, an Abstract Planning Graph P is created by using the Abstract Backward Planning Algorithm (ABP), then the abstract planning graph P is instantiated into a corresponding planning graph P by using the Forward Plan Instantiation Algorithm (FPI). The advantage is that in the preliminary ABP phase we produce a symbolic plan that is a pattern to direct the search of the concrete plan. This can be seen as a kind of informed search where the preliminary backward phase is useful to discover properties of the state-space that can be used to direct the subsequent forward phase. We evaluate the effectiveness of our ABP+FPI algorithm in the reduction of the explored planning domain by comparing it to a standard forward planning algorithm and applying both of them to a concrete business case study.
Learning Economic Parameters from Revealed Preferences
Venue: arXiv cs.GT 2014
Year: 2014

A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a utility function from revealed preference data. The goal here is to make use of past data describing the purchases of a utility maximizing agent when faced with certain prices and budget constraints in order to produce a hypothesis function that can accurately forecast the {\em future} behavior of the agent. In this work we advance this line of work by providing sample complexity guarantees and efficient algorithms for a number of important classes. By drawing a connection to recent advances in multi-class learning, we provide a computationally efficient algorithm with tight sample complexity guarantees ($Θ(d/ε)$ for the case of $d$ goods) for learning linear utility functions under a linear price model. This solves an open question in Zadimoghaddam and Roth (2012). Our technique yields numerous generalizations including the ability to learn other well-studied classes of utility functions, to deal with a misspecified model, and with non-linear prices.
The Grow-Shrink strategy for learning Markov network structures constrained by context-specific independences
Venue: arXiv cs.LG 2014
Year: 2014

Markov networks are models for compactly representing complex probability distributions. They are composed by a structure and a set of numerical weights. The structure qualitatively describes independences in the distribution, which can be exploited to factorize the distribution into a set of compact functions. A key application for learning structures from data is to automatically discover knowledge. In practice, structure learning algorithms focused on "knowledge discovery" present a limitation: they use a coarse-grained representation of the structure. As a result, this representation cannot describe context-specific independences. Very recently, an algorithm called CSPC was designed to overcome this limitation, but it has a high computational complexity. This work tries to mitigate this downside presenting CSGS, an algorithm that uses the Grow-Shrink strategy for reducing unnecessary computations. On an empirical evaluation, the structures learned by CSGS achieve competitive accuracies and lower computational complexity with respect to those obtained by CSPC.
Computation of a Tree 3-Spanner on Trapezoid Graphs
Venue: arXiv cs.DM 2014
Year: 2014

In a graph, a spanning tree is said to be a tree t-spanner of the graph if the distance between any two vertices in is at most times their distance in . The tree t-spanner has many applications in networks and distributed environments. In this paper, an algorithm is presented to find a tree -spanner on trapezoid graphs in time, where is the number of vertices of the graph.
Market Making with Decreasing Utility for Information
Venue: arXiv cs.GT 2014
Year: 2014

We study information elicitation in cost-function-based combinatorial prediction markets when the market maker's utility for information decreases over time. In the sudden revelation setting, it is known that some piece of information will be revealed to traders, and the market maker wishes to prevent guaranteed profits for trading on the sure information. In the gradual decrease setting, the market maker's utility for (partial) information decreases continuously over time. We design adaptive cost functions for both settings which: (1) preserve the information previously gathered in the market; (2) eliminate (or diminish) rewards to traders for the publicly revealed information; (3) leave the reward structure unaffected for other information; and (4) maintain the market maker's worst-case loss. Our constructions utilize mixed Bregman divergence, which matches our notion of utility for information.
Study on FLOWSIM and its Application for Isolated Signal-ized Intersection Assessment
Venue: arXiv cs.OH 2014
Year: 2014

Recently the traffic related problems have become strategically important, due to the continuously increasing vehicle number. As a result, microscopic simulation software has become an efficient method in traffic engineering for its cost-effectiveness and safety characteristics. In this paper, a new fuzzy logic based simulation software (FLOWSIM) is introduced, which can reflect the mixed traffic flow phenomenon in China better. The fuzzy logic based car-following model and lane-changing model are explained in detail. Furthermore, its applications for mixed traffic flow management in mid-size cities and for signalized intersection management assessment in large cities are illustrated by examples in China. Finally, further study objectives are discussed.
Pruning Techniques for the Stochastic on-time Arrival Problem\texorpdfstring -- An Experimental Study
Venue: arXiv cs.DS 2014
Year: 2014

Computing shortest paths is one of the most researched topics in algorithm engineering. Currently available algorithms compute shortest paths in mere fractions of a second on continental sized road networks. In the presence of unreliability, however, current algorithms fail to achieve results as impressive as for the static setting. In contrast to speed-up techniques for static route planning, current implementations for the stochastic on-time arrival problem require the computationally expensive step of solving convolution products. Running times can reach hours when considering large scale networks. We present a novel approach to reduce this immense computational effort of stochastic routing based on existing techniques for alternative routes. In an extensive experimental study, we show that the process of stochastic route planning can be speed-up immensely, without sacrificing much in terms of accuracy.
A New Model of Array Grammar for generating Connected Patterns on an Image Neighborhood
Venue: arXiv cs.FL 2014
Year: 2014

Study of patterns on images is recognized as an important step in characterization and classification of image. The ability to efficiently analyze and describe image patterns is thus of fundamental importance. The study of syntactic methods of describing pictures has been of interest for researchers. Array Grammars can be used to represent and recognize connected patterns. In any image the patterns are recognized using connected patterns. It is very difficult to represent all connected patterns (CP) even on a small 3 x 3 neighborhood in a pictorial way. The present paper proposes the model of array grammar capable of generating any kind of simple or complex pattern and derivation of connected pattern in an image neighborhood using the proposed grammar is discussed.
The DoF of the 3-user ($p,p+1$) MIMO Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

The \emph{degrees of freedom} (DoF) of the 3-user multiple-input multiple-output (MIMO) interference channel (IC) with full channel state information (CSI) and constant channel coefficients are characterized when linear filters are employed and $(p,p+1)$ antennas are deployed at the transmitters and receivers, respectively. The point of departure of this paper is the work of Wang et al, which conjectured but not proved the DoF for the configuration tackled in this work. In this work we prove the optimal DoF by means of a transmission scheme based on asymmetric complex signaling (ACS) together with symbol extensions in time and interference alignment (IA) concepts. The paper deals with the $p=2,3$ cases, providing the transmit and receive filters and the tools needed for proving the achievability of the DoF for other values of $p$.
Assessment Model for Opportunistic Routing (LatinCom)
Venue: arXiv cs.NI 2014
Year: 2014

Due to the increased capabilities of mobile devices and through wireless opportunistic contacts, users can experience new ways to share and retrieve content anywhere and anytime, even in the presence of link intermittency. Due to the significant number of available routing solutions, it is difficult to understand which one has the best performance, since all of them follow a different evaluation method. This paper proposes an assessment model, based on a new taxonomy, which comprises an evaluation guideline with performance metrics and experimental setup to aid designers in evaluating solutions through fair comparisons. Simulation results based on the proposed model revisit the performance results published by Epidemic, PROPHET, and Bubble Rap, showing how they perform under the same set of metrics and scenario.
Optimal Hub Labeling is NP-complete
Venue: arXiv cs.CC 2014
Year: 2014

Distance labeling is a preprocessing technique introduced by Peleg [Journal of Graph Theory, 33(3)] to speed up distance queries in large networks. Herein, each vertex receives a (short) label and, the distance between two vertices can be inferred from their two labels. One such preprocessing problem occurs in the hub labeling algorithm [Abraham et al., SODA'10]: the label of a vertex v is a set of vertices x (the "hubs") with their distance d(x,v) to v and the distance between any two vertices u and v is the sum of their distances to a common hub. The problem of assigning as few such hubs as possible was conjectured to be NP-hard, but no proof was known to date. We give a reduction from the well-known Vertex Cover problem on graphs to prove that finding an optimal hub labeling is indeed NP-hard.
Voronoi Game on Graphs
Venue: arXiv cs.DS 2014
Year: 2014

\textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two players {\it Voronoi game} where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding $k$ optimal facility locations of Player 2 given any placement of $m$ facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly $\mathcal{NP}$-complete for graphs. This proves that finding a winning strategy of P2 is $\mathcal{NP}$-complete. Consequently, we design an $1-\frac{1}{e}$ factor approximation algorithm, where $e \approx 2.718$.