OpenRaiser/Intern-Atlas huggingface dataset:
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
Venue: arXiv cs.DS 2015
Year: 2015

The Min-sum single machine scheduling problem (denoted 1||sum f_j) generalizes a large number of sequencing problems. The first constant approximation guarantees have been obtained only recently and are based on natural time-indexed LP relaxations strengthened with the so called Knapsack-Cover inequalities (see Bansal and Pruhs, Cheung and Shmoys and the recent 4+ε-approximation by Mestre and Verschae). These relaxations have an integrality gap of 2, since the Min-knapsack problem is a special case. No APX-hardness result is known and it is still conceivable that there exists a PTAS. Interestingly, the Lasserre hierarchy relaxation, when the objective function is incorporated as a constraint, reduces the integrality gap for the Min-knapsack problem to 1+ε. In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Lasserre hierarchy. We prove the first lower bound for this model by showing that the integrality gap is unbounded at level Ω(\sqrt{n}) even for a variant of the problem that is solvable in O(n log n) time by the Moore-Hodgson algorithm, namely Min-number of tardy jobs. We consider a natural formulation that incorporates the objective function as a constraint and prove the result by partially diagonalizing the matrix associated with the relaxation and exploiting this characterization.
Informative Data Projections: A Framework and Two Examples
Venue: arXiv cs.LG 2015
Year: 2015

Methods for Projection Pursuit aim to facilitate the visual exploration of high-dimensional data by identifying interesting low-dimensional projections. A major challenge is the design of a suitable quality metric of projections, commonly referred to as the projection index, to be maximized by the Projection Pursuit algorithm. In this paper, we introduce a new information-theoretic strategy for tackling this problem, based on quantifying the amount of information the projection conveys to a user given their prior beliefs about the data. The resulting projection index is a subjective quantity, explicitly dependent on the intended user. As a useful illustration, we developed this idea for two particular kinds of prior beliefs. The first kind leads to PCA (Principal Component Analysis), shining new light on when PCA is (not) appropriate. The second kind leads to a novel projection index, the maximization of which can be regarded as a robust variant of PCA. We show how this projection index, though non-convex, can be effectively maximized using a modified power method as well as using a semidefinite programming relaxation. The usefulness of this new projection index is demonstrated in comparative empirical experiments against PCA and a popular Projection Pursuit method.
An Empirical Study of Open Source Software Usability: The Industrial Perspective
Venue: arXiv cs.HC 2015
Year: 2015

Recent years have seen a sharp increase in the use of open source projects by common novice users; Open Source Software (OSS) is thus no longer a reserved arena for software developers and computer gurus. Although user-centered designs are gaining popularity in OSS, usability is still not considered as one of the prime objectives in many design scenarios. In this paper, we analyze industry users perception of usability factors, including understandability, learnability, operability and attractiveness, on OSS usability. The research model of this empirical study establishes the relationship between the key usability factors and OSS usability from industrial perspective. In order to conduct the study, a data set of 105 industry users is included. The results of the empirical investigation indicate the significance of the key factors for OSS usability.
Some Bounds on Communication Complexity of Gap Hamming Distance
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ($\mathsf{GHD}^n_{L, U}$): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$. Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$. Surprisingly, it can be computed with logarithmic precision: $$\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$. As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$-approximate deterministic $p$-pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$. Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$.
Multi-Cloud Resource Provisioning with Aneka: A Unified and Integrated Utilisation of Microsoft Azure and Amazon EC2 Instances
Venue: arXiv cs.DC 2015
Year: 2015

Many vendors are offering computing services on subscription basis via Infrastructure-as-a-Service (IaaS) model. Users can acquire resources from different providers and get the best of each of them to run their applications. However, deploying applications in multi-cloud environments is a complex task. Therefore, application platforms are needed to help developers to succeed. Aneka is one such platform that supports developers to program and deploy distributed applications in multi-cloud environments. It can be used to provision resources from different cloud providers and can be configured to request resources dynamically according to the needs of specific applications. This paper presents extensions incorporated in Aneka to support the deployment of applications in multi-cloud environments. The first extension shows the flexibility of Aneka architecture to add cloud providers. Specifically, we describe the addition of Microsoft Azure IaaS cloud provider. We also discuss the inclusion of public IPs to communicate resources located in different networks and the functionality of using PowerShell to automatize installation of Aneka on remote resources. We demonstrate how an application composed of independent tasks improves its total execution time when it is deployed in the multi-cloud environment created by Aneka using resources provisioned from Azure and EC2.
Stability Analysis of Network of Similar-Plants via Feedback Network
Venue: arXiv cs.SY 2015
Year: 2015

Here, we study a networked control system with similar linear time-invariant plants. Using master stability function method we propose a network optimization method to minimize the feedback network order in the sense Frobenius norm. Then we verify our results with numerical example. We show that this method outperforms the known feedback network optimization methods namely matching condition.
Computational Homogenization of Fresh Concrete Flow Around Reinforcing Bars
Venue: arXiv cs.CE 2015
Year: 2015

Motivated by casting of fresh concrete in reinforced concrete structures, we introduce a numerical model of a steady-state non-Newtonian fluid flow through a porous domain. Our approach combines homogenization techniques to represent the reinforced domain by the Darcy law with an interface coupling of the Stokes and Darcy flows through the Beavers-Joseph-Saffman conditions. The ensuing two-scale problem is solved by the Finite Element Method with consistent linearization and the results obtained from the homogenization approach are verified against fully resolved direct numerical simulations.
Evolving Models for Meso-Scale Structures
Venue: arXiv cs.SI 2015
Year: 2015

Real world complex networks are scale free and possess meso-scale properties like core-periphery and community structure. We study evolution of the core over time in real world networks. This paper proposes evolving models for both unweighted and weighted scale free networks having local and global core-periphery as well as community structure. Network evolves using topological growth, self growth, and weight distribution function. To validate the correctness of proposed models, we use K-shell and S-shell decomposition methods. Simulation results show that the generated unweighted networks follow power law degree distribution with droop head and heavy tail. Similarly, generated weighted networks follow degree, strength, and edge-weight power law distributions. We further study other properties of complex networks, such as clustering coefficient, nearest neighbor degree, and strength degree correlation.
An Efficient Bayesian PAPR Reduction Method for OFDM-Based Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of peak-to-average power ratio (PAPR) reduction in orthogonal frequency-division multiplexing (OFDM) based massive multiple-input multiple-output (MIMO) downlink systems. Specifically, given a set of symbol vectors to be transmitted to K users, the problem is to find an OFDM-modulated signal that has a low PAPR and meanwhile enables multiuser interference (MUI) cancellation. Unlike previous works that tackled the problem using convex optimization, we take a Bayesian approach and develop an efficient PAPR reduction method by exploiting the redundant degrees-of-freedom of the transmit array. The sought-after signal is treated as a random vector with a hierarchical truncated Gaussian mixture prior, which has the potential to encourage a low PAPR signal with most of its samples concentrated on the boundaries. A variational expectation-maximization (EM) strategy is developed to obtain estimates of the hyperparameters associated with the prior model, along with the signal. In addition, the generalized approximate message passing (GAMP) is embedded into the variational EM framework, which results in a significant reduction in computational complexity of the proposed algorithm. Simulation results show our proposed algorithm achieves a substantial performance improvement over existing methods in terms of both the PAPR reduction and computational complexity.
High Sensitivity Biosensor using Injection Locked Spin Torque Nano-Oscillators
Venue: arXiv cs.ET 2015
Year: 2015

With ever increasing research on magnetic nano systems it is shown to have great potential in the areas of magnetic storage, biosensing, magnetoresistive insulation etc. In the field of biosensing specifically Spin Valve sensors coupled with Magnetic Nanolabels is showing great promise due to noise immunity and energy efficiency [1]. In this paper we present the application of injection locked based Spin Torque Nano Oscillator (STNO) suitable for high resolution energy efficient labeled DNA Detection. The proposed STNO microarray consists of 20 such devices oscillating at different frequencies making it possible to multiplex all the signals using capacitive coupling. Frequency Division Multiplexing can be aided with Time division multiplexing to increase the device integration and decrease the readout time while maintaining the same efficiency in presence of constant input referred noise.
Digital LDO with Time-Interleaved Comparators for Fast Response and Low Ripple
Venue: arXiv cs.AR 2015
Year: 2015

On-chip voltage regulation using distributed Digital Low Drop Out (LDO) voltage regulators has been identified as a promising technique for efficient power-management for emerging multi-core processors. Digital LDOs (DLDO) can offer low voltage operation, faster transient response, and higher current efficiency. Response time as well as output voltage ripple can be reduced by increasing the speed of the dynamic comparators. However, the comparator offset steeply increases for high clock frequencies, thereby leading to enhanced variations in output voltage. In this work we explore the design of digital LDOs with multiple dynamic comparators that can overcome this bottleneck. In the proposed topology, we apply time-interleaved comparators with the same voltage threshold and uniform current step in order to accomplish the aforementioned features. Simulation based analysis shows that the DLDO with time-interleaved comparators can achieve better overall performance in terms of current efficiency, ripple and settling time. For a load step of 50mA, a DLDO with 8 time-interleaved comparators could achieve an output ripple of less than 5mV, while achieving a settling time of less than 0.5us. Load current dependant dynamic adjustment of clock frequency is proposed to maintain high current efficiency of ~97%.
An Algebraic Approach for Approximity
Venue: arXiv cs.LO 2015
Year: 2015

Comparison to traditionally accurate computing, approximate computing focuses on the rapidity of the satisfactory solution, but not the unnecessary accuracy of the solution. Approximate bisimularity is the approximate one corresponding to traditionally accurate bisimilarity. Based on the work of distances between basic processes, we propose an algebraic approach for distances between processes to support a whole process calculus CCS, which contains prefix, sum, composition, restriction, relabeling and recursion.
Influence diagrams for the optimization of a vehicle speed profile
Venue: arXiv cs.AI 2015
Year: 2015

Influence diagrams are decision theoretic extensions of Bayesian networks. They are applied to diverse decision problems. In this paper we apply influence diagrams to the optimization of a vehicle speed profile. We present results of computational experiments in which an influence diagram was used to optimize the speed profile of a Formula 1 race car at the Silverstone F1 circuit. The computed lap time and speed profiles correspond well to those achieved by test pilots. An extended version of our model that considers a more complex optimization function and diverse traffic constraints is currently being tested onboard a testing car by a major car manufacturer. This paper opens doors for new applications of influence diagrams.
Modeling Dynamic Relationships Between Characters in Literary Novels
Venue: arXiv cs.CL 2015
Year: 2015

Studying characters plays a vital role in computationally representing and interpreting narratives. Unlike previous work, which has focused on inferring character roles, we focus on the problem of modeling their relationships. Rather than assuming a fixed relationship for a character pair, we hypothesize that relationships are dynamic and temporally evolve with the progress of the narrative, and formulate the problem of relationship modeling as a structured prediction problem. We propose a semi-supervised framework to learn relationship sequences from fully as well as partially labeled data. We present a Markovian model capable of accumulating historical beliefs about the relationship and status changes. We use a set of rich linguistic and semantically motivated features that incorporate world knowledge to investigate the textual content of narrative. We empirically demonstrate that such a framework outperforms competitive baselines.
Enhancements in statistical spoken language translation by de-normalization of ASR results
Venue: arXiv cs.CL 2015
Year: 2015

Spoken language translation (SLT) has become very important in an increasingly globalized world. Machine translation (MT) for automatic speech recognition (ASR) systems is a major challenge of great interest. This research investigates that automatic sentence segmentation of speech that is important for enriching speech recognition output and for aiding downstream language processing. This article focuses on the automatic sentence segmentation of speech and improving MT results. We explore the problem of identifying sentence boundaries in the transcriptions produced by automatic speech recognition systems in the Polish language. We also experiment with reverse normalization of the recognized speech samples.
Retractable Prosthesis for Transfemoral Amputees Using Series Elastic Actuators and Force Control
Venue: arXiv cs.RO 2015
Year: 2015

We present a highly functional and cost-effective prosthesis for transfemoral amputees that uses series elastic actuators. These actuators allow for accurate force control, low impedance and large dynamic range. The design involves one active joint at the knee and a passive joint at the ankle. Additionally, the socket was designed using mirroring of compliances to ensure maximum comfort.
An analysis of the equational properties of the well-founded fixed point
Venue: arXiv cs.DM 2015
Year: 2015

Well-founded fixed points have been used in several areas of knowledge representation and reasoning and to give semantics to logic programs involving negation. They are an important ingredient of approximation fixed point theory. We study the logical properties of the (parametric) well-founded fixed point operation. We show that the operation satisfies several, but not all of the equational properties of fixed point operations described by the axioms of iteration theories.
Control approach to computing the feedback capacity for stationary finite dimensional Gaussian channels
Venue: arXiv cs.IT 2015
Year: 2015

We firstly extend the interpretation of feedback communication over stationary finite dimensional Gaussian channels as feedback control systems by showing that, the problem of finding stabilizing feedback controllers with maximal reliable transmission rate over Youla parameters coincides with the problem of finding strictly causal filters to achieve feedback capacity recently derived in [1]. The aforementioned interpretation provides an approach to construct deterministic feedback coding schemes (with double exponential decaying error probability). We next propose an asymptotic capacity-achieving upper bounds, which can be numerically evaluated by solving finite dimensional dual optimizations. From the filters that achieve upper bounds, we derive feasible filters which lead to a sequence of lower bounds. Thus, from the lower bound filters we obtain communication systems that achieve the lower bound rate. Extensive examples show the sequence of lower bounds is asymptotic capacity-achieving as well.
GrantMed: a new, international system for tracking grants and funding trends in the life sciences
Venue: arXiv cs.DL 2015
Year: 2015

Despite the success of PubMed and other search engines in managing the massive volume of biomedical literature and the retrieval of individual publications, grant-related data remains scattered and relatively inaccessible. This is problematic, as project and funding data has significant analytical value and could be integral to publication retrieval. Here, we introduce GrantMed, a searchable international database of biomedical grants that integrates some 20 million publications with the nearly 1.4 million research projects and 650 billion dollars of funding that made them possible. For any given topic in the life sciences, Grantmed provides instantaneous visualization of the past 30 years of dollars spent and projects awarded, along with detailed individual project descriptions, funding amounts, and links to investigators, research organizations, and resulting publications. It summarizes trends in funding and publication rates for areas of interest and merges data from various national grant databases to create one international grant tracking system. This information will benefit the research community and funding entities alike. Users can view trends over time or current projects underway and use this information to navigate the decision-making process in moving forward. They can view projects prior to publication and records of previous projects. Convenient access to this data for analytical purposes will be beneficial in many ways, helping to prevent project overlap, reduce funding redundancy, identify areas of success, accelerate dissemination of ideas, and expose knowledge gaps in moving forward. It is our hope that this will be a central resource for international life sciences research communities and the funding organizations that support them, ultimately streamlining progress.
SVC-based Multi-user Streamloading for Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we present an approach for joint rate allocation and quality selection for a novel video streaming scheme called streamloading. Streamloading is a recently developed method for delivering high quality video without violating copyright enforced restrictions on content access for video streaming. In regular streaming services, content providers restrict the amount of viewable video that users can download prior to playback. This approach can cause inferior user experience due to bandwidth variations, especially in mobile networks with varying capacity. In streamloading, the video is encoded using Scalable Video Coding, and users are allowed to pre-fetch enhancement layers and store them on the device, while base layers are streamed in a near real-time fashion ensuring that buffering constraints on viewable content are met. We begin by formulating the offline problem of jointly optimizing rate allocation and quality selection for streamloading in a wireless network. This motivates our proposed online algorithms for joint scheduling at the base station and segment quality selection at receivers. The results indicate that streamloading outperforms state-of-the-art streaming schemes in terms of the number of additional streams we can admit for a given video quality. Furthermore, the quality adaptation mechanism of our proposed algorithm achieves a higher performance than baseline algorithms with no (or limited) video-centric optimization of the base station's allocation of resources, e.g., proportional fairness.
Placement and Scheduling of Functions in Network Function Virtualization
Venue: arXiv cs.NI 2015
Year: 2015

The virtualization of Radio Access Networks (RANs) has been proposed as one of the important use cases of Network Function Virtualization (NFV). In VRAN!s (VRAN!s), some functions from a Base Station (BS), such as those which make up the Base Band Unit (BBU), may be implemented in a shared infrastructure located at either a data center or distributed in network nodes. For the latter option, one challenge is in deciding which subset of the available network nodes can be used to host the physical BBU servers (the placement problem), and then to which of the available physical BBUs each Remote Radio Head (RRH) should be assigned (the assignment problem). These two problems constitute what we refer to as the VRANPAP! (VRAN-PAP!). In this paper, we start by formally defining the VRAN-PAP! before formulating it as a Binary Integer Linear Program (BILP) whose objective is to minimize the server and front haul link setup costs as well as the latency between each RRH and its assigned BBU. Since the BILP could become computationally intractable, we also propose a greedy approximation for larger instances of the VRAN-PAP!. We perform simulations to compare both algorithms in terms of solution quality as well as computation time under varying network sizes and setup budgets.