OpenRaiser/Intern-Atlas huggingface dataset:
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a $(3/2-c)$-approximation algorithm for some fixed $c>0$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman & Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of $3/2$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.
Shape and Symmetry Induction for 3D Objects
Venue: arXiv cs.CV 2015
Year: 2015

Actions as simple as grasping an object or navigating around it require a rich understanding of that object's 3D shape from a given viewpoint. In this paper we repurpose powerful learning machinery, originally developed for object classification, to discover image cues relevant for recovering the 3D shape of potentially unfamiliar objects. We cast the problem as one of local prediction of surface normals and global detection of 3D reflection symmetry planes, which open the door for extrapolating occluded surfaces from visible ones. We demonstrate that our method is able to recover accurate 3D shape information for classes of objects it was not trained on, in both synthetic and real images.
Practical circuits with Physarum Wires
Venue: arXiv cs.ET 2015
Year: 2015

Purpose: Protoplasmic tubes of Physarum polycephalum, also know as Physarum Wires (PW), have been previously suggested as novel bio- electronic components. Until recently, practical examples of electronic circuits using PWs have been limited. These PWs have been shown to be self repairing, offering significant advantage over traditional electronic components. This article documents work performed to produce practical circuits using PWs. Method: We have demonstrated through manufacture and testing of hybrid circuits that PWs can be used to produce a variety of practical electronic circuits. A purality of different applications of PWs have been tested to show the universality of PWs in analogue and digital electronics. Results: Voltage dividers can be produced using a pair of PWs in series with an output voltage accurate to within 12%. PWs can also transmit analogue and digital data with a frequency of up to 19 kHz, which with the addition of a buffer, can drive high current circuits. We have demonstrated that PWs can last approximately two months, a 4 fold increase on previous literature. Protoplasmic tubes can be modified with the addition of conductive or magnetic nano-particles to provide changes in functionality. Conclusion This work has documented novel macro-scale data transmission through biological material; it has advanced the field of bio-electronics by providing a cheap and easy to grow conducting bio-material which may be used in future hybrid electronic technology.
Exploring Correlation between Labels to improve Multi-Label Classification
Venue: arXiv cs.LG 2015
Year: 2015

This paper attempts multi-label classification by extending the idea of independent binary classification models for each output label, and exploring how the inherent correlation between output labels can be used to improve predictions. Logistic Regression, Naive Bayes, Random Forest, and SVM models were constructed, with SVM giving the best results: an improvement of 12.9\% over binary models was achieved for hold out cross validation by augmenting with pairwise correlation probabilities of the labels.
Reordering GPU Kernel Launches to Enable Efficient Concurrent Execution
Venue: arXiv cs.DC 2015
Year: 2015

Contemporary GPUs allow concurrent execution of small computational kernels in order to prevent idling of GPU resources. Despite the potential concurrency between independent kernels, the order in which kernels are issued to the GPU will significantly influence the application performance. A technique for deriving suitable kernel launch orders is therefore presented, with the aim of reducing the total execution time. Experimental results indicate that the proposed method yields solutions that are well above the 90 percentile mark in the design space of all possible permutations of the kernel launch sequences.
Desktop to Cloud Migration of Scientific Computing Experiments
Venue: arXiv cs.DC 2015
Year: 2015

Scientific computing applications usually need huge amounts of computational power. The cloud provides interesting high-performance computing solutions, with its promise of virtually infinite resources on demand. However, migrating scientific computing problems to clouds and the re-creation of software environment on the vendor-supplied OS and cloud instances is often a laborious task. It is also assumed that the scientist who is performing the experiments has significant knowledge of computer science, cloud computing and the migration procedure, which is often not true. Considering these obstacles, we have designed a tool suite that migrates the complete software environment directly to the cloud. The developed desktop-to-cloud-migration (D2CM) tool supports transformation and migration of virtual machine images, reusable deployment description and life-cycle management for applications to be hosted on Amazon Cloud or compatible infrastructure such as Eucalyptus. The paper also presents an electrochemical case study and computational experiments targeted at designing modern supercapacitors. These experiments have extensively used the tool in drawing domain specific results. Detailed analysis of the case showed that D2CM tool not only simplifies the migration procedure for the scientists, but also helps them in optimizing the calculations and compute clusters, by providing them a new dimension -- cost-to-value of computational experiments.
Max-Cut under Graph Constraints
Venue: arXiv cs.DS 2015
Year: 2015

An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G and (ii) edge-weights on a complete undirected graph on the same vertex set. The objective is to find a subset of vertices satisfying some graph-based constraint in G that maximizes the total weight of edges in the cut. The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a 0.5-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali-Adams hierarchy. It can handle any graph constraint for which there is a (certain type of) dynamic program that exactly optimizes linear objectives. Using known decomposition results, these imply essentially the same approximation ratio for GCMC under constraints such as independent set, dominating set and connectivity on a planar graph G (more generally for bounded-genus or excluded-minor graphs).
Virtualization of 5G Cellular Networks as a Hierarchical Combinatorial Auction
Venue: arXiv cs.GT 2015
Year: 2015

Virtualization has been seen as one of the main evolution trends in the forthcoming fifth generation (5G) cellular networks which enables the decoupling of infrastructure from the services it provides. In this case, the roles of infrastructure providers (InPs) and mobile virtual network operators (MVNOs) can be logically separated and the resources (e.g., subchannels, power, and antennas) of a base station owned by an InP can be transparently shared by multiple MVNOs, while each MVNO virtually owns the entire BS. Naturally, the issue of resource allocation arises. In particular, the InP is required to abstract the physical resources into isolated slices for each MVNO who then allocates the resources within the slice to its subscribed users. In this paper, we aim to address this two-level hierarchical resource allocation problem while satisfying the requirements of efficient resource allocation, strict inter-slice isolation, and the ability of intra-slice customization. To this end, we design a hierarchical combinatorial auction mechanism, based on which a truthful and sub-efficient resource allocation framework is provided. Specifically, winner determination problems (WDPs) are formulated for the InP and MVNOs, and computationally tractable algorithms are proposed to solve these WDPs. Also, pricing schemes are designed to ensure incentive compatibility. The designed mechanism can achieve social efficiency in each level even if each party involved acts selfishly. Numerical results show the effectiveness of the proposed scheme.
Scalable BGP Prefix Selection for Effective Inter-domain Traffic Engineering
Venue: arXiv cs.NI 2015
Year: 2015

Inter-domain Traffic Engineering for multi-homed networks faces a scalability challenge, as the size of BGP routing table continue to grow. In this context, the choice of the best path must be made potentially for each destination prefix, requiring all available paths to be characterised (e.g., through measurements) and compared with each other. Fortunately, it is well-known that a few number of prefixes carry the larger part of the traffic. As a natural consequence, to engineer large volume of traffic only few prefixes need to be managed. Yet, traffic characteristics of a given prefix can greatly vary over time, and little is known on the dynamism of traffic at this aggregation level, including predicting the set of the most significant prefixes in the near future. %based on past observations. Sophisticated prediction methods won't scale in such context. In this paper, we study the relationship between prefix volume, stability, and predictability, based on recent traffic traces from nine different networks. Three simple and resource-efficient methods to select the prefixes associated with the most important foreseeable traffic volume are then proposed. Such proposed methods allow to select sets of prefixes with both excellent representativeness (volume coverage) and stability in time, for which the best routes are identified. The analysis carried out confirm the potential benefits of a route decision engine.
From Static to Dynamic Tag Population Estimation: An Extended Kalman Filter Perspective
Venue: arXiv cs.SY 2015
Year: 2015

Tag population estimation has recently attracted significant research attention due to its paramount importance on a variety of radio frequency identification (RFID) applications. However, most, if not all, of existing estimation mechanisms are proposed for the static case where tag population remains constant during the estimation process, thus leaving the more challenging dynamic case unaddressed, despite the fundamental importance of the latter case on both theoretical analysis and practical application. In order to bridge this gap, %based on \textit{dynamic framed-slotted ALOHA} (DFSA) protocol, we devote this paper to designing a generic framework of stable and accurate tag population estimation schemes based on Kalman filter for both static and dynamic RFID systems. %The objective is to devise estimation schemes and analyze the boundedness of estimation error. Technically, we first model the dynamics of RFID systems as discrete stochastic processes and leverage the techniques in extended Kalman filter (EKF) and cumulative sum control chart (CUSUM) to estimate tag population for both static and dynamic systems. By employing Lyapunov drift analysis, we mathematically characterise the performance of the proposed framework in terms of estimation accuracy and convergence speed by deriving the closed-form conditions on the design parameters under which our scheme can stabilise around the real population size with bounded relative estimation error that tends to zero with exponential convergence rate.
On randomization of neural networks as a form of post-learning strategy
Venue: arXiv cs.NE 2015
Year: 2015

Today artificial neural networks are applied in various fields - engineering, data analysis, robotics. While they represent a successful tool for a variety of relevant applications, mathematically speaking they are still far from being conclusive. In particular, they suffer from being unable to find the best configuration possible during the training process (local minimum problem). In this paper, we focus on this issue and suggest a simple, but effective, post-learning strategy to allow the search for improved set of weights at a relatively small extra computational cost. Therefore, we introduce a novel technique based on analogy with quantum effects occurring in nature as a way to improve (and sometimes overcome) this problem. Several numerical experiments are presented to validate the approach.
Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case
Venue: arXiv cs.LG 2015
Year: 2015

We demonstrate that, in the classical non-stochastic regret minimization problem with $d$ decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most $s$ decisions incur a nonzero outcome), we derive optimal regret bounds of different orders. Specifically, with gains, we obtain an optimal regret guarantee after $T$ stages of order $\sqrt{T\log s}$, so the classical dependency in the dimension is replaced by the sparsity size. With losses, we provide matching upper and lower bounds of order $\sqrt{Ts\log(d)/d}$, which is decreasing in $d$. Eventually, we also study the bandit setting, and obtain an upper bound of order $\sqrt{Ts\log (d/s)}$ when outcomes are losses. This bound is proven to be optimal up to the logarithmic factor $\sqrt{\log(d/s)}$.
Beyond OWL 2 QL in OBDA: Rewritings and Approximations (Extended Version)
Venue: arXiv cs.AI 2015
Year: 2015

Ontology-based data access (OBDA) is a novel paradigm facilitating access to relational data, realized by linking data sources to an ontology by means of declarative mappings. DL-Lite_R, which is the logic underpinning the W3C ontology language OWL 2 QL and the current language of choice for OBDA, has been designed with the goal of delegating query answering to the underlying database engine, and thus is restricted in expressive power. E.g., it does not allow one to express disjunctive information, and any form of recursion on the data. The aim of this paper is to overcome these limitations of DL-Lite_R, and extend OBDA to more expressive ontology languages, while still leveraging the underlying relational technology for query answering. We achieve this by relying on two well-known mechanisms, namely conservative rewriting and approximation, but significantly extend their practical impact by bringing into the picture the mapping, an essential component of OBDA. Specifically, we develop techniques to rewrite OBDA specifications with an expressive ontology to "equivalent" ones with a DL-Lite_R ontology, if possible, and to approximate them otherwise. We do so by exploiting the high expressive power of the mapping layer to capture part of the domain semantics of rich ontology languages. We have implemented our techniques in the prototype system OntoProx, making use of the state-of-the-art OBDA system Ontop and the query answering system Clipper, and we have shown their feasibility and effectiveness with experiments on synthetic and real-world data.
TGSum: Build Tweet Guided Multi-Document Summarization Dataset
Venue: arXiv cs.IR 2015
Year: 2015

The development of summarization research has been significantly hampered by the costly acquisition of reference summaries. This paper proposes an effective way to automatically collect large scales of news-related multi-document summaries with reference to social media's reactions. We utilize two types of social labels in tweets, i.e., hashtags and hyper-links. Hashtags are used to cluster documents into different topic sets. Also, a tweet with a hyper-link often highlights certain key points of the corresponding document. We synthesize a linked document cluster to form a reference summary which can cover most key points. To this aim, we adopt the ROUGE metrics to measure the coverage ratio, and develop an Integer Linear Programming solution to discover the sentence set reaching the upper bound of ROUGE. Since we allow summary sentences to be selected from both documents and high-quality tweets, the generated reference summaries could be abstractive. Both informativeness and readability of the collected summaries are verified by manual judgment. In addition, we train a Support Vector Regression summarizer on DUC generic multi-document summarization benchmarks. With the collected data as extra training resource, the performance of the summarizer improves a lot on all the test sets. We release this dataset for further research.
On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals
Venue: arXiv cs.DS 2015
Year: 2015

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al., who designed a greedy-like algorithm with length approximation ratio $4$. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio $\frac12$, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm.
An Introduction to Convolutional Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

The field of machine learning has taken a dramatic twist in recent times, with the rise of the Artificial Neural Network (ANN). These biologically inspired computational models are able to far exceed the performance of previous forms of artificial intelligence in common machine learning tasks. One of the most impressive forms of ANN architecture is that of the Convolutional Neural Network (CNN). CNNs are primarily used to solve difficult image-driven pattern recognition tasks and with their precise yet simple architecture, offers a simplified method of getting started with ANNs. This document provides a brief introduction to CNNs, discussing recently published papers and newly formed techniques in developing these brilliantly fantastic image recognition models. This introduction assumes you are familiar with the fundamentals of ANNs and machine learning.
TennisVid2Text: Fine-grained Descriptions for Domain Specific Videos
Venue: arXiv cs.CV 2015
Year: 2015

Automatically describing videos has ever been fascinating. In this work, we attempt to describe videos from a specific domain - broadcast videos of lawn tennis matches. Given a video shot from a tennis match, we intend to generate a textual commentary similar to what a human expert would write on a sports website. Unlike many recent works that focus on generating short captions, we are interested in generating semantically richer descriptions. This demands a detailed low-level analysis of the video content, specially the actions and interactions among subjects. We address this by limiting our domain to the game of lawn tennis. Rich descriptions are generated by leveraging a large corpus of human created descriptions harvested from Internet. We evaluate our method on a newly created tennis video data set. Extensive analysis demonstrate that our approach addresses both semantic correctness as well as readability aspects involved in the task.
Simultaneous Private Learning of Multiple Concepts
Venue: arXiv cs.DS 2015
Year: 2015

We investigate the direct-sum problem in the context of differentially private PAC learning: What is the sample complexity of solving $k$ learning tasks simultaneously under differential privacy, and how does this cost compare to that of solving $k$ learning tasks without privacy? In our setting, an individual example consists of a domain element $x$ labeled by $k$ unknown concepts $(c_1,\ldots,c_k)$. The goal of a multi-learner is to output $k$ hypotheses $(h_1,\ldots,h_k)$ that generalize the input examples. Without concern for privacy, the sample complexity needed to simultaneously learn $k$ concepts is essentially the same as needed for learning a single concept. Under differential privacy, the basic strategy of learning each hypothesis independently yields sample complexity that grows polynomially with $k$. For some concept classes, we give multi-learners that require fewer samples than the basic strategy. Unfortunately, however, we also give lower bounds showing that even for very simple concept classes, the sample cost of private multi-learning must grow polynomially in $k$.
Study of Memristor-based Oscillatory Neural Networks using PPV modeling
Venue: arXiv cs.ET 2015
Year: 2015

Memristor-based oscillator is becoming promising thanks to its inherent NDR (Negative Differential Region) property and compact circuit structure. This paves the way to the large scale oscillatory neural network (ONN) and the realization of pattern recognition based on its global synchronization. However, the simulation of large scale ONN encounters the problem of long simulation time because of the large number of oscillators. Here we propose a highly efficient method to abstract the phase sensitivity characteristic of the memristor-based oscillator, i.e., its PPV (Perturbation Projection Vector), which allows reducing considerably the complexity of ONN simulation, and speeding up the simulation more than 2000 times. Our study also reveals the impact of the circuit parameters on the pattern recognition accuracy and the robustness against the frequency mismatch.
Dynamic Clustering and ON/OFF Strategies for Wireless Small Cell Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, a novel cluster-based approach for maximizing the energy efficiency of wireless small cell networks is proposed. A dynamic mechanism is proposed to group locally-coupled small cell base stations (SBSs) into clusters based on location and traffic load. Within each formed cluster, SBSs coordinate their transmission parameters to minimize a cost function which captures the tradeoffs between energy efficiency and flow level performance, while satisfying their users' quality-of-service requirements. Due to the lack of inter-cluster communications, clusters compete with one another in order to improve the overall network's energy efficiency. This inter-cluster competition is formulated as a noncooperative game between clusters that seek to minimize their respective cost functions. To solve this game, a distributed learning algorithm is proposed using which clusters autonomously choose their optimal transmission strategies based on local information. It is shown that the proposed algorithm converges to a stationary mixed-strategy distribution which constitutes an epsilon-coarse correlated equilibrium for the studied game. Simulation results show that the proposed approach yields significant performance gains reaching up to 36% of reduced energy expenditures and up to 41% of reduced fractional transfer time compared to conventional approaches.
Two Results on Discontinuous Input Processing
Venue: arXiv cs.FL 2015
Year: 2015

First, we show that universality and other properties of general jumping finite automata are undecidable, which answers a question asked by Meduna and Zemek in 2012. Second, we close the study raised by Černo and Mráz in 2010 by proving that clearing restarting automata using contexts of size two can accept binary non-context-free languages.