OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed Approximation Algorithm for the Metric Uncapacitated Facility Location Problem in the Congest Model
Venue: arXiv cs.DC 2011
Year: 2011

We present a randomized distributed approximation algorithm for the metric uncapacitated facility location problem. The algorithm is executed on a bipartite graph in the Congest model yielding a (1.861 + epsilon) approximation factor, where epsilon is an arbitrary small positive constant. It needs O(n^{3/4}log_{1+epsilon}^2(n) communication rounds with high probability (n denoting the number of facilities and clients). To the best of our knowledge, our algorithm currently has the best approximation factor for the facility location problem in a distributed setting. It is based on a greedy sequential approximation algorithm by Jain et al. (J. ACM 50(6), pages: 795-824, 2003). The main difficulty in executing this sequential algorithm lies in dealing with situations, where multiple facilities are eligible for opening, but (in order to preserve the approximation factor of the sequential algorithm) only a subset of them can actually be opened. Note that while the presented runtime bound of our algorithm is "with high probability", the approximation factor is not "in expectation" but always guaranteed to be (1.861 + epsilon). Thus, our main contribution is a sublinear time selection mechanism that, while increasing the approximation factor by an arbitrary small additive term, allows us to decide which of the eligible facilities to open.
A Framework for the Evaluation of Worst-Case System Efficiency
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we present FASE (Fast Asynchronous Systems Evaluation), a tool for evaluating worst-case efficiency of asynchronous systems. This tool implements some well-established results in the setting of a timed CCS-like process algebra: PAFAS (a Process Algebra for Faster Asynchronous Systems). Moreover, we discuss some new solutions that are useful to improve the applicability of FASE to concrete meaningful examples. We finally use fase to evaluate the efficiency of three different implementations of a bounded buffer and compare our results with previous ones obtained when the same implementations have been contrasted according to an efficiency preorder.
Comparison Latent Semantic and WordNet Approach for Semantic Similarity Calculation
Venue: arXiv cs.IR 2011
Year: 2011

Information exchange among many sources in Internet is more autonomous, dynamic and free. The situation drive difference view of concepts among sources. For example, word 'bank' has meaning as economic institution for economy domain, but for ecology domain it will be defined as slope of river or lake. In this aper, we will evaluate latent semantic and WordNet approach to calculate semantic similarity. The evaluation will be run for some concepts from different domain with reference by expert or human. Result of the evaluation can provide a contribution for mapping of concept, query rewriting, interoperability, etc.
Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm
Venue: arXiv cs.DS 2011
Year: 2011

We show that the pseudoflow algorithm for maximum flow is particularly efficient for the bipartite matching problem both in theory and in practice. We develop several implementations of the pseudoflow algorithm for bipartite matching, and compare them over a wide set of benchmark instances to state-of-the-art implementations of push-relabel and augmenting path algorithms that are specifically designed to solve these problems. The experiments show that the pseudoflow variants are in most cases faster than the other algorithms. We also show that one particular implementation---the matching pseudoflow algorithm---is theoretically efficient. For a graph with $n$ nodes, $m$ arcs, $n_1$ the size of the smaller set in the bipartition, and the maximum matching value $κ\leq n_1$, the algorithm's complexity given input in the form of adjacency lists is $O(\min{n_1κ,m} + \sqrtκ\min{κ^2,m})$. Similar algorithmic ideas are shown to work for an adaptation of Hopcroft and Karp's bipartite matching algorithm with the same complexity. Using boolean operations on words of size $λ$, the complexity of the pseudoflow algorithm is further improved to $O(\min{n_1κ, \frac{n_1n_2}λ, m} + κ^2 + \frac{κ^{2.5}}λ)$. This run time is faster than for previous algorithms such as Cheriyan and Mehlhorn's algorithm of complexity $O(\frac{n^{2.5}}λ)$.
Experimental Study of the Shortest Reset Word of Random Automata
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we describe an approach to finding the shortest reset word of a finite synchronizing automaton by using a SAT solver. We use this approach to perform an experimental study of the length of the shortest reset word of a finite synchronizing automaton. The largest automata we considered had 100 states. The results of the experiments allow us to formulate a hypothesis that the length of the shortest reset word of a random finite automaton with $n$ states and 2 input letters with high probability is sublinear with respect to $n$ and can be estimated as $1.95 n^{0.55}.$
Abstracting Abstract Machines: A Systematic Approach to Higher-Order Program Analysis
Venue: arXiv cs.PL 2011
Year: 2011

Predictive models are fundamental to engineering reliable software systems. However, designing conservative, computable approximations for the behavior of programs (static analyses) remains a difficult and error-prone process for modern high-level programming languages. What analysis designers need is a principled method for navigating the gap between semantics and analytic models: analysis designers need a method that tames the interaction of complex languages features such as higher-order functions, recursion, exceptions, continuations, objects and dynamic allocation. We contribute a systematic approach to program analysis that yields novel and transparently sound static analyses. Our approach relies on existing derivational techniques to transform high-level language semantics into low-level deterministic state-transition systems (with potentially infinite state spaces). We then perform a series of simple machine refactorings to obtain a sound, computable approximation, which takes the form of a non-deterministic state-transition systems with finite state spaces. The approach scales up uniformly to enable program analysis of realistic language features, including higher-order functions, tail calls, conditionals, side effects, exceptions, first-class continuations, and even garbage collection.
Individual-based stability in hedonic games depending on the best or worst players
Venue: arXiv cs.GT 2011
Year: 2011

We consider coalition formation games in which each player has preferences over the other players and his preferences over coalitions are based on the best player ($\mathcal{B}$-/B-hedonic games) or the worst player ($\mathcal{W}$/W-hedonic games) in the coalition. We show that for $\mathcal{B}$-hedonic games, an individually stable partition is guaranteed to exist and can be computed efficiently. Similarly, there exists a polynomial-time algorithm which returns a Nash stable partition (if one exists) for $\mathcal{B}$-hedonic games with strict preferences. Both $\mathcal{W}$- and W-hedonic games are equivalent if individual rationality is assumed. It is also shown that for B- or $\mathcal{W}$-hedonic games, checking whether a Nash stable partition or an individually stable partition exists is NP-complete even in some cases for strict preferences. We identify a key source of intractability in compact coalition formation games in which preferences over players are extended to preferences over coalitions.
Property Testing for Cyclic Groups and Beyond
Venue: arXiv cs.DS 2011
Year: 2011

This paper studies the problem of testing if an input (Gamma,*), where Gamma is a finite set of unknown size and * is a binary operation over Gamma given as an oracle, is close to a specified class of groups. Friedl et al. [Efficient testing of groups, STOC'05] have constructed an efficient tester using poly(log|Gamma|) queries for the class of abelian groups. We focus in this paper on subclasses of abelian groups, and show that these problems are much harder: Omega(|Gamma|^{1/6}) queries are necessary to test if the input is close to a cyclic group, and Omega(|Gamma|^c) queries for some constant c are necessary to test more generally if the input is close to an abelian group generated by k elements, for any fixed integer k>0. We also show that knowledge of the size of the ground set Gamma helps only for k=1, in which case we construct an efficient tester using poly(log|Gamma|) queries; for any other value k>1 the query complexity remains Omega(|Gamma|^c). All our upper and lower bounds hold for both the edit distance and the Hamming distance. These are, to the best of our knowledge, the first nontrivial lower bounds for such group-theoretic problems in the property testing model and, in particular, they imply the first exponential separations between the classical and quantum query complexities of testing closeness to classes of groups.
Chebyshev Polynomial Approximation for Distributed Signal Processing
Venue: arXiv cs.DC 2011
Year: 2011

Unions of graph Fourier multipliers are an important class of linear operators for processing signals defined on graphs. We present a novel method to efficiently distribute the application of these operators to the high-dimensional signals collected by sensor networks. The proposed method features approximations of the graph Fourier multipliers by shifted Chebyshev polynomials, whose recurrence relations make them readily amenable to distributed computation. We demonstrate how the proposed method can be used in a distributed denoising task, and show that the communication requirements of the method scale gracefully with the size of the network.
Secure Data Processing in a Hybrid Cloud
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing has made it possible for a user to be able to select a computing service precisely when needed. However, certain factors such as security of data and regulatory issues will impact a user's choice of using such a service. A solution to these problems is the use of a hybrid cloud that combines a user's local computing capabilities (for mission- or organization-critical tasks) with a public cloud (for less influential tasks). We foresee three challenges that must be overcome before the adoption of a hybrid cloud approach: 1) data design: How to partition relations in a hybrid cloud? The solution to this problem must account for the sensitivity of attributes in a relation as well as the workload of a user; 2) data security: How to protect a user's data in a public cloud with encryption while enabling query processing over this encrypted data? and 3) query processing: How to execute queries efficiently over both, encrypted and unencrypted data? This paper addresses these challenges and incorporates their solutions into an add-on tool for a Hadoop and Hive based cloud computing infrastructure.
New Heuristic Rounding Approaches to the Quadratic Assignment Problem
Venue: arXiv cs.CC 2011
Year: 2011

Quadratic assignment problem is one of the great challenges in combinatorial optimization. It has many applications in Operations research and Computer Science. In this paper, the author extends the most-used rounding approach to a one-parametric optimization model for the quadratic assignment problems. A near-optimum parameter is also predestinated. The numerical experiments confirm the efficiency.
Security Risks and Modern Cyber Security Technologies for Corporate Networks
Venue: arXiv cs.CR 2011
Year: 2011

This article aims to highlight current trends on the market of corporate antivirus solutions. Brief overview of modern security threats that can destroy IT environment is provided as well as a typical structure and features of antivirus suits for corporate users presented on the market. The general requirements for corporate products are determined according to the last report from av-comparatives.org [1]. The detailed analysis of new features is provided based on an overview of products available on the market nowadays. At the end, an enumeration of modern trends in antivirus industry for corporate users completes this article. Finally, the main goal of this article is to stress an attention about new trends suggested by AV vendors in their solutions in order to protect customers against newest security threats.
Submodular Cost Allocation Problem and Applications
Venue: arXiv cs.DS 2011
Year: 2011

We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set $V$ and $k$ non-negative submodular set functions $f_1 ,..., f_k$ on $V$. The objective is to partition $V$ into $k$ (possibly empty) sets $A_1 ,..., A_k$ such that the sum $\sum_{i=1}^k f_i(A_i)$ is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lovász-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for several problems. In particular, we give a $(1.5 - 1/k)$-approximation for the hypergraph multiway partition problem. We also give a $\min\{2(1-1/k), H_Δ\}$-approximation for the hypergraph multiway cut problem when $Δ$ is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.
In Search of Autocorrelation Based Vocal Cord Cues for Speaker Identification
Venue: arXiv cs.HC 2011
Year: 2011

In this paper we investigate a technique to find out vocal source based features from the LP residual of speech signal for automatic speaker identification. Autocorrelation with some specific lag is computed for the residual signal to derive these features. Compared to traditional features like MFCC, PLPCC which represent vocal tract information, these features represent complementary vocal cord information. Our experiment in fusing these two sources of information in representing speaker characteristics yield better speaker identification accuracy. We have used Gaussian mixture model (GMM) based speaker modeling and results are shown on two public databases to validate our proposition.
A Cloud-based Approach for Context Information Provisioning
Venue: arXiv cs.DC 2011
Year: 2011

As a result of the phenomenal proliferation of modern mobile Internet-enabled devices and the widespread utilization of wireless and cellular data networks, mobile users are increasingly requiring services tailored to their current context. High-level context information is typically obtained from context services that aggregate raw context information sensed by various sensors and mobile devices. Given the massive amount of sensed data, traditional context services are lacking the necessary resources to store and process these data, as well as to disseminate high-level context information to a variety of potential context consumers. In this paper, we propose a novel framework for context information provisioning, which relies on deploying context services on the cloud and using context brokers to mediate between context consumers and context services using a publish/subscribe model. Moreover, we describe a multi-attributes decision algorithm for the selection of potential context services that can fulfill context consumers' requests for context information. The algorithm calculates the score of each context service, per context information type, based on the quality-of-service (QoS) and quality-of-context information (QoC) requirements expressed by the context consumer. One of the benefits of the approach is that context providers can scale up and down, in terms of cloud resources they use, depending on current demand for context information. Besides, the selection algorithm allows ranking context services by matching their QoS and QoC offers against the QoS and QoC requirements of the context consumer.
More about Base Station Location Games
Venue: arXiv cs.NI 2011
Year: 2011

This paper addresses the problem of locating base stations in a certain area which is highly populated by mobile stations; each mobile station is assumed to select the closest base station. Base stations are modeled by players who choose their best location for maximizing their uplink throughput. The approach of this paper is to make some simplifying assumptions in order to get interpretable analytical results and insights to the problem under study. Specifically, a relatively complete Nash equilibrium (NE) analysis is conducted (existence, uniqueness, determination, and efficiency). Then, assuming that the base station location can be adjusted dynamically, the best-response dynamics and reinforcement learning algorithm are applied, discussed, and illustrated through numerical results.
EXPTIME Tableaux for the Coalgebraic mu-Calculus
Venue: arXiv cs.LO 2011
Year: 2011

The coalgebraic approach to modal logic provides a uniform framework that captures the semantics of a large class of structurally different modal logics, including e.g. graded and probabilistic modal logics and coalition logic. In this paper, we introduce the coalgebraic mu-calculus, an extension of the general (coalgebraic) framework with fixpoint operators. Our main results are completeness of the associated tableau calculus and EXPTIME decidability for guarded formulas. Technically, this is achieved by reducing satisfiability to the existence of non-wellfounded tableaux, which is in turn equivalent to the existence of winning strategies in parity games. Our results are parametric in the underlying class of models and yield, as concrete applications, previously unknown complexity bounds for the probabilistic mu-calculus and for an extension of coalition logic with fixpoints.
Data-Distributed Weighted Majority and Online Mirror Descent
Venue: arXiv cs.LG 2011
Year: 2011

In this paper, we focus on the question of the extent to which online learning can benefit from distributed computing. We focus on the setting in which $N$ agents online-learn cooperatively, where each agent only has access to its own data. We propose a generic data-distributed online learning meta-algorithm. We then introduce the Distributed Weighted Majority and Distributed Online Mirror Descent algorithms, as special cases. We show, using both theoretical analysis and experiments, that compared to a single agent: given the same computation time, these distributed algorithms achieve smaller generalization errors; and given the same generalization errors, they can be $N$ times faster.
The Deterministic Sum Capacity of a Multiple Access Channel Interfering with a Point to Point Link
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we use the linear deterministic approximation model to study a two user multiple access channel mutually interfering with a point to point link, which represents a basic setup of a cellular system. We derive outer bounds on the achievable sum rate and construct coding schemes achieving the outer bounds. For a large parameter range, the sum capacity is identical to the sum capacity of the interference channel obtained by silencing the weaker user in the multiple access channel. For other interference configurations, the sum rate can be increased using interference alignment, which exploits the channel gain difference of the users in the multiple access channel. From these results, lower bounds on the generalized degrees of freedom for the Gaussian counterpart are derived.
Entropy rate calculations of algebraic measures
Venue: arXiv cs.IT 2011
Year: 2011

Let $K = \{0,1,...,q-1\}$. We use a special class of translation invariant measures on $K^\mathbb{Z}$ called algebraic measures to study the entropy rate of a hidden Markov processes. Under some irreducibility assumptions of the Markov transition matrix we derive exact formulas for the entropy rate of a general $q$ state hidden Markov process derived from a Markov source corrupted by a specific noise model. We obtain upper bounds on the error when using an approximation to the formulas and numerically compute the entropy rates of two and three state hidden Markov models.
Joint Network and LDPC Coding for Bi-directional Relaying
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider joint network and LDPC coding for practically implementing the denosie-and-forward protocol over bi-directional relaying. the closed-form expressions for computing the log-likelihood ratios of the network-coded codewords have been derived for both real and complex multiple-access channels. It is revealed that the equivalent channel observed at the relay is an asymmetrical channel, where the channel input is the XOR form of the two source nodes.
On Pseudocodewords and Decision Regions of Linear Programming Decoding of HDPC Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we explore the decision regions of Linear Programming (LP) decoding. We compare the decision regions of an LP decoder, a Belief Propagation (BP) decoder and the optimal Maximum Likelihood (ML) decoder. We study the effect of minimal-weight pseudocodewords on LP decoding. We present global optimization as a method for finding the minimal pseudoweight of a given code as well as the number of minimal-weight generators. We present a complete pseudoweight distribution for the [24; 12; 8] extended Golay code, and provide justifications of why the pseudoweight distribution alone cannot be used for obtaining a tight upper bound on the error probability.
Broadcast Strategies with Probabilistic Delivery Guarantee in Multi-Channel Multi-Interface Wireless Mesh Networks
Venue: arXiv cs.NI 2011
Year: 2011

Multi-channel multi-interface Wireless Mesh Networks permit to spread the load across orthogonal channels to improve network capacity. Although broadcast is vital for many layer-3 protocols, proposals for taking advantage of multiple channels mostly focus on unicast transmissions. In this paper, we propose broadcast algorithms that fit any channel and interface assignment strategy. They guarantee that a broadcast packet is delivered with a minimum probability to all neighbors. Our simulations show that the proposed algorithms efficiently limit the overhead.
Dynamic Backward Slicing of Rewriting Logic Computations
Venue: arXiv cs.LO 2011
Year: 2011

Trace slicing is a widely used technique for execution trace analysis that is effectively used in program debugging, analysis and comprehension. In this paper, we present a backward trace slicing technique that can be used for the analysis of Rewriting Logic theories. Our trace slicing technique allows us to systematically trace back rewrite sequences modulo equational axioms (such as associativity and commutativity) by means of an algorithm that dynamically simplifies the traces by detecting control and data dependencies, and dropping useless data that do not influence the final result. Our methodology is particularly suitable for analyzing complex, textually-large system computations such as those delivered as counter-example traces by Maude model-checkers.