OpenRaiser/Intern-Atlas huggingface dataset:
Using Network Coding to Achieve the Capacity of Deterministic Relay Networks with Relay Messages
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we derive the capacity of the deterministic relay networks with relay messages. We consider a network which consists of five nodes, four of which can only communicate via the fifth one. However, the fifth node is not merely a relay as it may exchange private messages with the other network nodes. First, we develop an upper bound on the capacity region based on the notion of a single sided genie. In the course of the achievability proof, we also derive the deterministic capacity of a 4-user relay network (without private messages at the relay). The capacity achieving schemes use a combination of two network coding techniques: the Simple Ordering Scheme (SOS) and Detour Schemes (DS). In the SOS, we order the transmitted bits at each user such that the bi-directional messages will be received at the same channel level at the relay, while the basic idea behind the DS is that some parts of the message follow an indirect path to their respective destinations. This paper, therefore, serves to show that user cooperation and network coding can enhance throughput, even when the users are not directly connected to each other.
Robust Face Recognition via Adaptive Sparse Representation
Venue: arXiv cs.CV 2014
Year: 2014

Sparse Representation (or coding) based Classification (SRC) has gained great success in face recognition in recent years. However, SRC emphasizes the sparsity too much and overlooks the correlation information which has been demonstrated to be critical in real-world face recognition problems. Besides, some work considers the correlation but overlooks the discriminative ability of sparsity. Different from these existing techniques, in this paper, we propose a framework called Adaptive Sparse Representation based Classification (ASRC) in which sparsity and correlation are jointly considered. Specifically, when the samples are of low correlation, ASRC selects the most discriminative samples for representation, like SRC; when the training samples are highly correlated, ASRC selects most of the correlated and discriminative samples for representation, rather than choosing some related samples randomly. In general, the representation model is adaptive to the correlation structure, which benefits from both $\ell_1$-norm and $\ell_2$-norm. Extensive experiments conducted on publicly available data sets verify the effectiveness and robustness of the proposed algorithm by comparing it with state-of-the-art methods.
Automatic Annotation of Axoplasmic Reticula in Pursuit of Connectomes
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present a new pipeline which automatically identifies and annotates axoplasmic reticula, which are small subcellular structures present only in axons. We run our algorithm on the Kasthuri11 dataset, which was color corrected using gradient-domain techniques to adjust contrast. We use a bilateral filter to smooth out the noise in this data while preserving edges, which highlights axoplasmic reticula. These axoplasmic reticula are then annotated using a morphological region growing algorithm. Additionally, we perform Laplacian sharpening on the bilaterally filtered data to enhance edges, and repeat the morphological region growing algorithm to annotate more axoplasmic reticula. We track our annotations through the slices to improve precision, and to create long objects to aid in segment merging. This method annotates axoplasmic reticula with high precision. Our algorithm can easily be adapted to annotate axoplasmic reticula in different sets of brain data by changing a few thresholds. The contribution of this work is the introduction of a straightforward and robust pipeline which annotates axoplasmic reticula with high precision, contributing towards advancements in automatic feature annotations in neural EM data.
Reusing an FM-index
Venue: arXiv cs.DS 2014
Year: 2014

Intuitively, if two strings $S_1$ and $S_2$ are sufficiently similar and we already have an FM-index for $S_1$ then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for $S_2$. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.
A Technology for BigData Analysis Task Description using Domain-Specific Languages
Venue: arXiv cs.DC 2014
Year: 2014

The article presents a technology for dynamic knowledge-based building of Domain-Specific Languages (DSL) to describe data-intensive scientific discovery tasks using BigData technology. The proposed technology supports high level abstract definition of analytic and simulation parts of the task as well as integration into the composite scientific solutions. Automatic translation of the abstract task definition enables seamless integration of various data sources within single solution.
Enhanced aodv route discovery and route establishment for qos provision for real time transmission in manet
Venue: arXiv cs.NI 2014
Year: 2014

MANET is a temporary connection of mobile nodes via wireless links having no centralized base station. We developed a protocol with an enhanced route discovery mechanism that avoids the pre-transmission delay. When a source node wants to communicate with another node, it broadcast RREQ. EAODV give priority to the source node of real time transmission. When RREQ packet send to neighbor node, for real time transmission it accept route request on priority basis and the drop ratio of packets decreased, then throughput increases by receiving more packets at destination and delivery ratio also increased through these QOS improved.
Joint Latency and Cost Optimization for Erasure-coded Data Center Storage
Venue: arXiv cs.DC 2014
Year: 2014

Modern distributed storage systems offer large capacity to satisfy the exponentially increasing need of storage space. They often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. This paper provides an insightful upper bound on the average service delay of such erasure-coded storage with arbitrary service time distribution and consisting of multiple heterogeneous files. Not only does the result supersede known delay bounds that only work for a single file or homogeneous files, it also enables a novel problem of joint latency and storage cost minimization over three dimensions: selecting the erasure code, placement of encoded chunks, and optimizing scheduling policy. The problem is efficiently solved via the computation of a sequence of convex approximations with provable convergence. We further prototype our solution in an open-source, cloud storage deployment over three geographically distributed data centers. Experimental results validate our theoretical delay analysis and show significant latency reduction, providing valuable insights into the proposed latency-cost tradeoff in erasure-coded storage.
Clinching Auctions Beyond Hard Budget Constraints
Venue: arXiv cs.GT 2014
Year: 2014

Constraints on agent's ability to pay play a major role in auction design for any setting where the magnitude of financial transactions is sufficiently large. Those constraints have been traditionally modeled in mechanism design as \emph{hard budget}, i.e., mechanism is not allowed to charge agents more than a certain amount. Yet, real auction systems (such as Google AdWords) allow more sophisticated constraints on agents' ability to pay, such as \emph{average budgets}. In this work, we investigate the design of Pareto optimal and incentive compatible auctions for agents with \emph{constrained quasi-linear utilities}, which captures more realistic models of liquidity constraints that the agents may have. Our result applies to a very general class of allocation constraints known as polymatroidal environments, encompassing many settings of interest such as multi-unit auctions, matching markets, video-on-demand and advertisement systems. Our design is based Ausubel's \emph{clinching framework}. Incentive compatibility and feasibility with respect to ability-to-pay constraints are direct consequences of the clinching framework. Pareto-optimality, on the other hand, is considerably more challenging, since the no-trade condition that characterizes it depends not only on whether agents have their budgets exhausted or not, but also on prices {at} which the goods are allocated. In order to get a handle on those prices, we introduce novel concepts of dropping prices and saturation. These concepts lead to our main structural result which is a characterization of the tight sets in the clinching auction outcome and its relation to dropping prices.
Sustaining IT PMOs during Cycles of Global Recession
Venue: arXiv cs.SE 2014
Year: 2014

Growth in the number of PMOs established by the industry over last decade and ever growing body of literature on PMO related research in academia is a clear indication that there is very clear interest of researchers, practitioners and industries across the globe to understand and explore value propositions of PMO. However, there is still a lack of consensus on many critical aspects of PMOs. While there are many PMOs being established, but there are also many being closed and disbanded, which is definitely a matter of concern. In industry environment, a narrow majority of PMOs are well-regarded by their organizations and are seen as contributing business value, many of the others are still struggling to show value for money and some are failing, causing a high mortality rate among PMOs. This paper is the result of a study undertaken to get a deeper understanding of factors that may be causing mortality and failure of PMOs. Post Implementation Reviews of 4-failed & 3-challenged PMOs in IT-Industry were carried out with concerned Project Managers & PMO-staff, using grounded theory research method, with support from the concerned enterprise from IT-Industry.
Correlated Jamming in a Joint Source Channel Communication System
Venue: arXiv cs.IT 2014
Year: 2014

We study correlated jamming in joint source-channel communication systems. An i.i.d. source is to be communicated over a memoryless channel in the presence of a correlated jammer with non-causal knowledge of user transmission. This user-jammer interaction is modeled as a zero sum game. A set of conditions on the source and the channel is provided for the existence of a Nash equilibrium for this game, where the user strategy is uncoded transmission and the jammer strategy is i.i.d jamming. This generalizes a well-known example of uncoded communication of a Gaussian sources over Gaussian channels with additive jamming. Another example, of a Binary Symmetric source over a Binary Symmetric channel with jamming, is provided as a validation of this result.
Rapid prototyping for sling design optimization
Venue: arXiv cs.CE 2014
Year: 2014

This paper deals with combination of two modern engineering methods in order to optimise the shape of a representative casting product. The product being analysed is a sling, which is used to attach pulling rope in timber transportation. The first step was 3D modelling and static stress/strain analysis using CAD/CAE software NX4. The slinger shape optimization was performed using Traction method, by means of software Optishape-TS. To define constraints for shape optimization, FEA software FEMAP was used. The mould pattern with optimized 3D shape was then prepared using Fused Deposition Modelling (FDM) Rapid prototyping method. The sling mass decreased by 20%, while signifficantly better stress distribution was achieved, with maximum stress 3.5 times less than initial value. The future researches should use 3D scanning technology in order to provide more accurate 3D model of initial part. Results of this research can be used by toolmakers in order to engage FEA/RP technology to design and manufacture lighter products with acceptable stress distribution.
Multi-Target Regression via Random Linear Target Combinations
Venue: arXiv cs.LG 2014
Year: 2014

Multi-target regression is concerned with the simultaneous prediction of multiple continuous target variables based on the same set of input variables. It arises in several interesting industrial and environmental application domains, such as ecological modelling and energy forecasting. This paper presents an ensemble method for multi-target regression that constructs new target variables via random linear combinations of existing targets. We discuss the connection of our approach with multi-label classification algorithms, in particular RA$k$EL, which originally inspired this work, and a family of recent multi-label classification algorithms that involve output coding. Experimental results on 12 multi-target datasets show that it performs significantly better than a strong baseline that learns a single model for each target using gradient boosting and compares favourably to multi-objective random forest approach, which is a state-of-the-art approach. The experiments further show that our approach improves more when stronger unconditional dependencies exist among the targets.
Optimising Trade-offs Among Stakeholders in Ad Auctions
Venue: arXiv cs.GT 2014
Year: 2014

We examine trade-offs among stakeholders in ad auctions. Our metrics are the revenue for the utility of the auctioneer, the number of clicks for the utility of the users and the welfare for the utility of the advertisers. We show how to optimize linear combinations of the stakeholder utilities, showing that these can be tackled through a GSP auction with a per-click reserve price. We then examine constrained optimization of stakeholder utilities. We use simulations and analysis of real-world sponsored search auction data to demonstrate the feasible trade-offs, examining the effect of changing the allowed number of ads on the utilities of the stakeholders. We investigate both short term effects, when the players do not have the time to modify their behavior, and long term equilibrium conditions. Finally, we examine a combinatorially richer constrained optimization problem, where there are several possible allowed configurations (templates) of ad formats. This model captures richer ad formats, which allow using the available screen real estate in various ways. We show that two natural generalizations of the GSP auction rules to this domain are poorly behaved, resulting in not having a symmetric Nash equilibrium or having one with poor welfare. We also provide positive results for restricted cases.
Compression for Quadratic Similarity Queries: Finite Blocklength and Practical Schemes
Venue: arXiv cs.IT 2014
Year: 2014

We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem - the minimal compression rate and the error exponent - were found in a previous work, in this paper we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: The gain (amplitude) of the vector is compressed via scalar quantization and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated and they converge to the asymptotic values as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.
Finding safe strategies for competitive diffusion on trees
Venue: arXiv cs.DM 2014
Year: 2014

We study the two-player safe game of Competitive Diffusion, a game-theoretic model for the diffusion of technologies or influence through a social network. In game theory, safe strategies are mixed strategies with a minimal expected gain against unknown strategies of the opponents. Safe strategies for competitive diffusion lead to maximum spread of influence in the presence of uncertainty about the other players. We study the safe game on two specific classes of trees, spiders and complete trees, and give tight bounds on the minimal expected gain. We then use these results to give an algorithm which suggests a safe strategy for a player on any tree. We test this algorithm on randomly generated trees, and show that it finds strategies that are close to optimal.
Lexicon Infused Phrase Embeddings for Named Entity Resolution
Venue: arXiv cs.CL 2014
Year: 2014

Most state-of-the-art approaches for named-entity recognition (NER) use semi supervised information in the form of word clusters and lexicons. Recently neural network-based language models have been explored, as they as a byproduct generate highly informative vector representations for words, known as word embeddings. In this paper we present two contributions: a new form of learning word embeddings that can leverage information from relevant lexicons to improve the representations, and the first system to use neural word embeddings to achieve state-of-the-art results on named-entity recognition in both CoNLL and Ontonotes NER. Our system achieves an F1 score of 90.90 on the test set for CoNLL 2003---significantly better than any previous system trained on public data, and matching a system employing massive private industrial query-log data.
New Techniques and Tighter Bounds for Local Computation Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

Given an input $x$, and a search problem $F$, local computation algorithms (LCAs) implement access to specified locations of $y$ in a legal output $y \in F(x)$, using polylogarithmic time and space. Mansour et al., (2012), had previously shown how to convert certain online algorithms to LCAs. In this work, we expand on that line of work and develop new techniques for designing LCAs and bounding their space and time complexity. Our contributions are fourfold: (1) We significantly improve the running times and space requirements of LCAs for previous results, (2) we expand and better define the family of online algorithms which can be converted to LCAs using our techniques, (3) we show that our results apply to a larger family of graphs than that of previous results, and (4) our proofs are simpler and more concise than the previous proof methods. For example, we show how to construct LCAs that require $O(\log{n}\log\log{n})$ space and $O(\log^2{n})$ time (and expected time $O(\log\log{n})$) for problems such as maximal matching on a large family of graphs, as opposed to the henceforth best results that required $O(\log^3{n})$ space and $O(\log^4{n})$ time, and applied to a smaller family of graphs.
Concurrent bandits and cognitive radio networks
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of multiple users targeting the arms of a single multi-armed stochastic bandit. The motivation for this problem comes from cognitive radio networks, where selfish users need to coexist without any side communication between them, implicit cooperation or common control. Even the number of users may be unknown and can vary as users join or leave the network. We propose an algorithm that combines an $ε$-greedy learning rule with a collision avoidance mechanism. We analyze its regret with respect to the system-wide optimum and show that sub-linear regret can be obtained in this setting. Experiments show dramatic improvement compared to other algorithms for this setting.
A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines
Venue: arXiv cs.CC 2014
Year: 2014

In the paper "The complexity of mean flow time scheduling problems with release times", by Baptiste, Brucker, Chrobak, Dürr, Kravchenko and Sourd, the authors claimed to prove strong NP-hardness of the scheduling problem $P|pmtn,r_j|\sum C_j$, namely multiprocessor preemptive scheduling where the objective is to minimize the mean flow time. We point out a serious error in their proof and give a new proof of strong NP-hardness for this problem.
A Logical Framework for Systems Biology
Venue: arXiv cs.LO 2014
Year: 2014

We propose a novel approach for the formal verification of biological systems based on the use of a modal linear logic. We show how such a logic can be used, with worlds as instants of time, as an unified framework to encode both biological systems and temporal properties of their dynamic behaviour. To illustrate our methodology, we consider a model of the P53/Mdm2 DNA-damage repair mechanism. We prove several properties that are important for such a model to satisfy and serve to illustrate the promise of our approach. We formalize the proofs of these properties in the Coq Proof Assistant, with the help of a Lambda Prolog prover for partial automation of the proofs.
Strong Converse and Second-Order Asymptotics of Channel Resolvability
Venue: arXiv cs.IT 2014
Year: 2014

We study the problem of channel resolvability for fixed i.i.d. input distributions and discrete memoryless channels (DMCs), and derive the strong converse theorem for any DMCs that are not necessarily full rank. We also derive the optimal second-order rate under a condition. Furthermore, under the condition that a DMC has the unique capacity achieving input distribution, we derive the optimal second-order rate of channel resolvability for the worst input distribution.
Online Colored Bin Packing
Venue: arXiv cs.DS 2014
Year: 2014

In the Colored Bin Packing problem a sequence of items of sizes up to $1$ arrives to be packed into bins of unit capacity. Each item has one of $c\geq 2$ colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins. In the important special case when all items have size zero, we characterize the optimal value to be equal to color discrepancy. As our main result, we give an (asymptotically) 1.5-competitive algorithm which is optimal. In fact, the algorithm always uses at most $\lceil1.5\cdot OPT\rceil$ bins and we show a matching lower bound of $\lceil1.5\cdot OPT\rceil$ for any value of $OPT\geq 2$. In particular, the absolute ratio of our algorithm is $5/3$ and this is optimal. For items of unrestricted sizes we give an asymptotically $3.5$-competitive algorithm. When the items have sizes at most $1/d$ for a real $d \geq 2$ the asymptotic competitive ratio is $1.5+d/(d-1)$. We also show that classical algorithms First Fit, Best Fit and Worst Fit are not constant competitive, which holds already for three colors and small items. In the case of two colors---the Black and White Bin Packing problem---we prove that all Any Fit algorithms have absolute competitive ratio $3$. When the items have sizes at most $1/d$ for a real $d \geq 2$ we show that the Worst Fit algorithm is absolutely $(1+d/(d-1))$-competitive.