OpenRaiser/Intern-Atlas huggingface dataset:
On the parameter $μ_{21}$ of a complete bipartite graph
Venue: arXiv cs.DM 2012
Year: 2012

A proper edge $t$-coloring of a graph $G$ is a coloring of edges of $G$ with colors $1,2,...,t$ such that all colors are used, and no two adjacent edges receive the same color. The set of colors of edges incident with a vertex $x$ is called a spectrum of $x$. An arbitrary nonempty subset of consecutive integers is called an interval. Suppose that all edges of a graph $G$ are colored in the game of Alice and Bob with asymmetric distribution of roles. Alice determines the number $t$ of colors in the future proper edge coloring of $G$ and aspires to minimize the number of vertices with an interval spectrum in it. Bob colors edges of $G$ with $t$ colors and aspires to maximize that number. $μ_{21}(G)$ is equal to the number of vertices of $G$ with an interval spectrum at the finish of the game on the supposition that both players choose their best strategies. In this paper, for arbitrary positive integers $m$ and $n$, the exact value of the parameter $μ_{21}(K_{m,n})$ is found.
On the equivalence of game and denotational semantics for the probabilistic mu-calculus
Venue: arXiv cs.LO 2012
Year: 2012

The probabilistic (or quantitative) modal mu-calculus is a fixed-point logic de- signed for expressing properties of probabilistic labeled transition systems (PLTS). Two semantics have been studied for this logic, both assigning to every process state a value in the interval [0,1] representing the probability that the property expressed by the formula holds at the state. One semantics is denotational and the other is a game semantics, specified in terms of two-player stochastic games. The two semantics have been proved to coincide on all finite PLTS's, but the equivalence of the two semantics on arbitrary models has been open in literature. In this paper we prove that the equivalence indeed holds for arbitrary infinite models, and thus our result strengthens the fruitful connection between denotational and game semantics. Our proof adapts the unraveling or unfolding method, a general proof technique for proving result of parity games by induction on their complexity.
Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs
Venue: arXiv cs.DM 2012
Year: 2012

A proper edge $t$-coloring of a graph $G$ is a coloring of edges of $G$ with colors $1,2,...,t$ such that each of $t$ colors is used, and adjacent edges are colored differently. The set of colors of edges incident with a vertex $x$ of $G$ is called a spectrum of $x$. A proper edge $t$-coloring of a graph $G$ is interval for its vertex $x$ if the spectrum of $x$ is an interval of integers. A proper edge $t$-coloring of a graph $G$ is persistent-interval for its vertex $x$ if the spectrum of $x$ is an interval of integers beginning from the color 1. For graphs $G$ from some classes of graphs, we obtain estimates for the possible number of vertices for which a proper edge $t$-coloring of $G$ can be interval or persistent-interval.
Least Information Modeling for Information Retrieval
Venue: arXiv cs.IR 2012
Year: 2012

We proposed a Least Information theory (LIT) to quantify meaning of information in probability distribution changes, from which a new information retrieval model was developed. We observed several important characteristics of the proposed theory and derived two quantities in the IR context for document representation. Given probability distributions in a collection as prior knowledge, LI Binary (LIB) quantifies least information due to the binary occurrence of a term in a document whereas LI Frequency (LIF) measures least information based on the probability of drawing a term from a bag of words. Three fusion methods were also developed to combine LIB and LIF quantities for term weighting and document ranking. Experiments on four benchmark TREC collections for ad hoc retrieval showed that LIT-based methods demonstrated very strong performances compared to classic TF*IDF and BM25, especially for verbose queries and hard search topics. The least information theory offers a new approach to measuring semantic quantities of information and provides valuable insight into the development of new IR models.
Performance Analysis of Decode-and-Forward Relaying in Gamma-Gamma Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

Decode-and-forward (DF) cooperative communication based on free space optical (FSO) links is studied in this letter. We analyze performance of the DF protocol in the FSO links following the Gamma-Gamma distribution. The cumulative distribution function (CDF) and probability density function (PDF) of a random variable containing mixture of the Gamma- Gamma and Gaussian random variables is derived. By using the derived CDF and PDF, average bit error rate of the DF relaying is obtained.
Signed and Minus Domination in Complete Multipartite Graphs
Venue: arXiv cs.DM 2012
Year: 2012

In this paper we determine the exact values of the signed domination number, signed total domination number, and minus domination number of complete multipartite graphs, which substantially generalizes some previous results obtained for special subclasses of complete multipartite graphs such as cliques and complete bipartite graphs.
Modes of Convergence for Term Graph Rewriting
Venue: arXiv cs.LO 2012
Year: 2012

Term graph rewriting provides a simple mechanism to finitely represent restricted forms of infinitary term rewriting. The correspondence between infinitary term rewriting and term graph rewriting has been studied to some extent. However, this endeavour is impaired by the lack of an appropriate counterpart of infinitary rewriting on the side of term graphs. We aim to fill this gap by devising two modes of convergence based on a partial order respectively a metric on term graphs. The thus obtained structures generalise corresponding modes of convergence that are usually studied in infinitary term rewriting. We argue that this yields a common framework in which both term rewriting and term graph rewriting can be studied. In order to substantiate our claim, we compare convergence on term graphs and on terms. In particular, we show that the modes of convergence on term graphs are conservative extensions of the corresponding modes of convergence on terms and are preserved under unravelling term graphs to terms. Moreover, we show that many of the properties known from infinitary term rewriting are preserved. This includes the intrinsic completeness of both modes of convergence and the fact that convergence via the partial order is a conservative extension of the metric convergence.
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
Venue: arXiv cs.DS 2012
Year: 2012

Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection is hard to approximate within $α_{GW} + ε\approx 0.8786$ under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that Max Bisection is approximable within $α_{GW}-ε$, i.e., the bisection constraint (essentially) does not make Max Cut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of Max 2-Sat. Our approximation ratio for this problem exactly matches the optimal approximation ratio for Max 2-Sat, i.e., $α_{LLZ} + ε\approx 0.9401$, showing that the bisection constraint does not make Max 2-Sat harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.
High availability using virtualization - 3RC
Venue: arXiv cs.SY 2012
Year: 2012

High availability has always been one of the main problems for a data center. Till now high availability was achieved by host per host redundancy, a highly expensive method in terms of hardware and human costs. A new approach to the problem can be offered by virtualization. Using virtualization, it is possible to achieve a redundancy system for all the services running on a data center. This new approach to high availability allows the running virtual machines to be distributed over a small number of servers, by exploiting the features of the virtualization layer: start, stop and move virtual machines between physical hosts. The 3RC system is based on a finite state machine, providing the possibility to restart each virtual machine over any physical host, or reinstall it from scratch. A complete infrastructure has been developed to install operating system and middleware in a few minutes. To virtualize the main servers of a data center, a new procedure has been developed to migrate physical to virtual hosts. The whole Grid data center SNS-PISA is running at the moment in virtual environment under the high availability system.
Enhanced Algebraic Error Control for Random Linear Network Coding
Venue: arXiv cs.IT 2012
Year: 2012

Error control is significant to network coding, since when unchecked, errors greatly deteriorate the throughput gains of network coding and seriously undermine both reliability and security of data. Two families of codes, subspace and rank metric codes, have been used to provide error control for random linear network coding. In this paper, we enhance the error correction capability of these two families of codes by using a novel two-tier decoding scheme. While the decoding of subspace and rank metric codes serves a second-tier decoding, we propose to perform a first-tier decoding on the packet level by taking advantage of Hamming distance properties of subspace and rank metric codes. This packet-level decoding can also be implemented by intermediate nodes to reduce error propagation. To support the first-tier decoding, we also investigate Hamming distance properties of three important families of subspace and rank metric codes, Gabidulin codes, Kotter--Kschischang codes, and Mahdavifar--Vardy codes. Both the two-tier decoding scheme and the Hamming distance properties of these codes are novel to the best of our knowledge.
Generalized Complexity of ALC Subsumption
Venue: arXiv cs.LO 2012
Year: 2012

The subsumption problem with respect to terminologies in the description logic ALC is EXPTIME-complete. We investigate the computational complexity of fragments of this problem by means of allowed Boolean operators. Hereto we make use of the notion of clones in the context of Post's lattice. Furthermore we consider all four possible quantifier combinations for each fragment parameterized by a clone. We will see that depending on what quantifiers are available the classification will be either tripartite or a quartering.
Integrated Development Environment Gesture for modeling workflow diagrams
Venue: arXiv cs.HC 2012
Year: 2012

The current software development tools show the same form of interaction as when they started back, in the mid 70's. However, since the appearance of visual languages and due to their own nature, they can be handled by tools which have different input methods to conventional ones. By incorporating new motion detection technology, it is intended that new forms of interaction are established. Interactions which respond to the free movement of hands, therefore the software's developer will have a substantial improvement in the user experience.
DNS-based Ingress Load Balancing: An Experimental Evaluation
Venue: arXiv cs.NI 2012
Year: 2012

Multihomed services can load-balance their incoming connection requests using DNS, resolving the name of the server with different addresses depending on the link load that corresponds to each address. Previous work has studied a number of problems with this approach, e.g., due to Time-to-Live duration violations and client proximity to local DNS servers. In this paper, we experimentally evaluate a DNS-based ingress traffic engineering system that we deployed at Georgia Tech. Our objective is to understand whether simple and robust load balancing algorithms can be accurate in practice, despite aforementioned problems with DNS-based load balancing methods. In particular, we examine the impact of various system parameters and of the main workload characteristics. We show that a window-based measurement scheme can be fairly accurate in practice, as long as its window duration has been appropriately configured.
Development of application for discovering and binding to published geospatial processes in distributed environments
Venue: arXiv cs.SE 2012
Year: 2012

Nowadays, society has recognized that the lack of access to spatial data and tools for their analysis is the limiting factor of economic development. It came to the realization that without the single information space, which is implemented in the form of spatial data infrastructures, a progressive business development is impossible. Spatial data infrastructures will support a variety of tasks, which requires the binding of geospatial information from multiple sources. In the last few years, the rate of progress in spatial data collection was higher, than in management and analysis of data. Infrastructures allow the accumulated data to be available to large groups of users, and infrastructure of analysis allows the data to be effectively used for such tasks as municipal planning, science research, etc. Moreover, free access to the information resources and instruments of analysis will serve as an additional impulse to development of application models in corresponding areas of expertise. The goal of this paper is to indicate possible solutions to the client-side problems of spatial data analysis in distributed environments, using the developing application for data analysis as an example.
A note on a problem in communication complexity
Venue: arXiv cs.CC 2012
Year: 2012

In this note, we prove a version of Tarui's Theorem in communication complexity, namely $PH^{cc} \subseteq BP\cdot PP^{cc}$. Consequently, every measure for $PP^{cc}$ leads to a measure for $PH^{cc}$, subsuming a result of Linial and Shraibman that problems with high mc-rigidity lie outside the polynomial hierarchy. By slightly changing the definition of mc-rigidity (arbitrary instead of uniform distribution), it is then evident that the class $M^{cc}$ of problems with low mc-rigidity equals $BP\cdot PP^{cc}$. As $BP\cdot PP^{cc} \subseteq PSPACE^{cc}$, this rules out the possibility, that had been left open, that even polynomial space is contained in $M^{cc}$.
Pebble games with algebraic rules
Venue: arXiv cs.LO 2012
Year: 2012

We define a general framework of partition games for formulating two-player pebble games over finite structures. We show that one particular such game, which we call the invertible-map game, yields a family of polynomial-time approximations of graph isomorphism that is strictly stronger than the well-known Weisfeiler-Lehman method. The general framework we introduce includes as special cases the pebble games for finite-variable logics with and without counting. It also includes a matrix-equivalence game, introduced here, which characterises equivalence in the finite-variable fragments of matrix-rank logic. We show that the equivalence defined by the invertible-map game is a refinement of the equivalence defined by each of these games for finite-variable logics.
ViQIE: A New Approach for Visual Query Interpretation and Extraction
Venue: arXiv cs.IR 2012
Year: 2012

Web services are accessed via query interfaces which hide databases containing thousands of relevant information. User's side, distant database is a black box which accepts query and returns results, there is no way to access database schema which reflect data and query meanings. Hence, web services are very autonomous. Users view this autonomy as a major drawback because they need often to combine query capabilities of many web services at the same time. In this work, we will present a new approach which allows users to benefit of query capabilities of many web services while respecting autonomy of each service. This solution is a new contribution in Information Retrieval research axe and has proven good performances on two standard datasets.
Partisan Asymmetries in Online Political Activity
Venue: arXiv cs.SI 2012
Year: 2012

We examine partisan differences in the behavior, communication patterns and social interactions of more than 18,000 politically-active Twitter users to produce evidence that points to changing levels of partisan engagement with the American online political landscape. Analysis of a network defined by the communication activity of these users in proximity to the 2010 midterm congressional elections reveals a highly segregated, well clustered partisan community structure. Using cluster membership as a high-fidelity (87% accuracy) proxy for political affiliation, we characterize a wide range of differences in the behavior, communication and social connectivity of left- and right-leaning Twitter users. We find that in contrast to the online political dynamics of the 2008 campaign, right-leaning Twitter users exhibit greater levels of political activity, a more tightly interconnected social structure, and a communication network topology that facilitates the rapid and broad dissemination of political information.
An Overview on Clustering Methods
Venue: arXiv cs.DS 2012
Year: 2012

Clustering is a common technique for statistical data analysis, which is used in many fields, including machine learning, data mining, pattern recognition, image analysis and bioinformatics. Clustering is the process of grouping similar objects into different groups, or more precisely, the partitioning of a data set into subsets, so that the data in each subset according to some defined distance measure. This paper covers about clustering algorithms, benefits and its applications. Paper concludes by discussing some limitations.
Subset Typicality Lemmas and Improved Achievable Regions in Multiterminal Source Coding
Venue: arXiv cs.IT 2012
Year: 2012

Consider the following information theoretic setup wherein independent codebooks of N correlated random variables are generated according to their respective marginals. The problem of determining the conditions on the rates of codebooks to ensure the existence of at least one codeword tuple which is jointly typical with respect to a given joint density (called the multivariate covering lemma) has been studied fairly well and the associated rate regions have found applications in several source coding scenarios. However, several multiterminal source coding applications, such as the general multi-user Gray-Wyner network, require joint typicality only within subsets of codewords transmitted. Motivated by such applications, we ask ourselves the conditions on the rates to ensure the existence of at least one codeword tuple which is jointly typical within subsets according to given per subset joint densities. This report focuses primarily on deriving a new achievable rate region for this problem which strictly improves upon the direct extension of the multivariate covering lemma, which has quite popularly been used in several earlier work. Towards proving this result, we derive two important results called `subset typicality lemmas' which can potentially have broader applicability in more general scenarios beyond what is considered in this report. We finally apply the results therein to derive a new achievable region for the general multi-user Gray-Wyner network.
Combinatorial coloring of 3-colorable graphs
Venue: arXiv cs.DM 2012
Year: 2012

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to $\tO(n^{4/11})$ colors. This is the first combinatorial improvement of Blum's $\tO(n^{3/8})$ bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite approaches. The current best bound is $O(n^{0.2072})$ colors by Chlamtac from FOCS'07. We now bring it down to $O(n^{0.2038})$ colors.
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Venue: arXiv cs.DS 2012
Year: 2012

In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc disjoint paths between any pair of vertices. We give a simple (1 + 1/k)-approximation to the unweighted variant of the problem, where all arcs of G have the same cost. This improves on the 1 + 2/k approximation of Gabow et al. [GGTW09]. Similar to the 2-approximation algorithm for this problem [FJ81], our algorithm simply takes the union of a k in-arborescence and a k out-arborescence. The main difference is in the selection of the two arborescences. Here, inspired by the recent applications of the rounding by sampling method (see e.g. [AGM+ 10, MOS11, OSS11, AKS12]), we select the arborescences randomly by sampling from a distribution on unions of k arborescences that is defined based on an extreme point solution of the linear programming relaxation of the problem. In the analysis, we crucially utilize the sparsity property of the extreme point solution to upper-bound the size of the union of the sampled arborescences. To complement the algorithm, we also show that the integrality gap of the minimum cost strongly connected subgraph problem (i.e., when k = 1) is at least 3/2 - c, for any c > 0. Our integrality gap instance is inspired by the integrality gap example of the asymmetric traveling salesman problem [CGK06], hence providing further evidence of connections between the approximability of the two problems.
Converting online algorithms to local computation algorithms
Venue: arXiv cs.DS 2012
Year: 2012

We propose a general method for converting online algorithms to local computation algorithms by selecting a random permutation of the input, and simulating running the online algorithm. We bound the number of steps of the algorithm using a query tree, which models the dependencies between queries. We improve previous analyses of query trees on graphs of bounded degree, and extend the analysis to the cases where the degrees are distributed binomially, and to a special case of bipartite graphs. Using this method, we give a local computation algorithm for maximal matching in graphs of bounded degree, which runs in time and space O(log^3 n). We also show how to convert a large family of load balancing algorithms (related to balls and bins problems) to local computation algorithms. This gives several local load balancing algorithms which achieve the same approximation ratios as the online algorithms, but run in O(log n) time and space. Finally, we modify existing local computation algorithms for hypergraph 2-coloring and k-CNF and use our improved analysis to obtain better time and space bounds, of O(log^4 n), removing the dependency on the maximal degree of the graph from the exponent.
Index Coding - An Interference Alignment Perspective
Venue: arXiv cs.IT 2012
Year: 2012

The index coding problem is studied from an interference alignment perspective, providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between multiple unicast index coding where each message is desired by exactly one receiver, and multiple groupcast index coding where a message can be desired by multiple receivers, which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with multiple groupcast settings where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate $\frac{1}{L+1}$ per message when each destination desires at least $L$ messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding.