OpenRaiser/Intern-Atlas huggingface dataset:
Optimization and Reoptimization in Scheduling Problems
Venue: arXiv cs.DS 2015
Year: 2015

Parallel machine scheduling has been extensively studied in the past decades, with applications ranging from production planning to job processing in large computing clusters. In this work we study some of these fundamental optimization problems, as well as their parameterized and reoptimization variants. We first present improved bounds for job scheduling on unrelated parallel machines, with the objective of minimizing the latest completion time (makespan) of the schedule. We consider the subclass of fully-feasible instances, in which the processing time of each job, on any machine, does not exceed the minimum makespan. The problem is known to be hard to approximate within factor 4/3 already in this subclass. Although fully-feasible instances are hard to identify, we give a polynomial time algorithm that yields for such instances a schedule whose makespan is better than twice the optimal, the best known ratio for general instances. Moreover, we show that our result is robust under small violations of feasibility constraints. We further study the power of parameterization. We show that makespan minimization on unrelated machines admits a parameterized approximation scheme, where the parameter used is the number of processing times that are large relative to the latest completion time of the schedule. We also present an FPT algorithm for the graph-balancing problem, which corresponds to the instances of the restricted assignment problem where each job can be processed on at most 2 machines. Finally, motivated by practical scenarios, we initiate the study of reoptimization in job scheduling on identical and uniform machines, with the objective of minimizing the makespan. We develop reapproximation algorithms that yield in both models the best possible approximation ratio of $(1+ε)$, for any $ε>0$, with respect to the minimum makespan.
Tightly-Held and Ephemeral Psychometrics: Password and Passphrase Authentication Utilizing User-Supplied Constructs of Self
Venue: arXiv cs.HC 2015
Year: 2015

This research investigates the role of passwords and passphrases as valid authentication methodologies. Specifically, this research dispels earlier work that ignores information-theoretic lessons learned from cognitive and social psychology and psycholinguistics, and extends and enriches the current password security model.
A Hybrid Approach to Domain-Specific Entity Linking
Venue: arXiv cs.IR 2015
Year: 2015

The current state-of-the-art Entity Linking (EL) systems are geared towards corpora that are as heterogeneous as the Web, and therefore perform sub-optimally on domain-specific corpora. A key open problem is how to construct effective EL systems for specific domains, as knowledge of the local context should in principle increase, rather than decrease, effectiveness. In this paper we propose the hybrid use of simple specialist linkers in combination with an existing generalist system to address this problem. Our main findings are the following. First, we construct a new reusable benchmark for EL on a corpus of domain-specific conversations. Second, we test the performance of a range of approaches under the same conditions, and show that specialist linkers obtain high precision in isolation, and high recall when combined with generalist linkers. Hence, we can effectively exploit local context and get the best of both worlds.
A macro placer algorithm for chip design
Venue: arXiv cs.DS 2015
Year: 2015

There is a set of rectangular macros with given dimensions, and there are wires connecting some pairs (or sets) of them. We have a placement area where these macros should be placed without overlaps in order to minimize the total length of wires. We present a heuristic algorithm which utilizes a special data structure for representing two dimensional stepfunctions. This results in fast integral computation and function modification over rectangles. Our heuristics, especially our data structure for two-dimensional functions, may be useful in other applications, as well.
Hierarchical Deep Learning Architecture For 10K Objects Classification
Venue: arXiv cs.CV 2015
Year: 2015

Evolution of visual object recognition architectures based on Convolutional Neural Networks & Convolutional Deep Belief Networks paradigms has revolutionized artificial Vision Science. These architectures extract & learn the real world hierarchical visual features utilizing supervised & unsupervised learning approaches respectively. Both the approaches yet cannot scale up realistically to provide recognition for a very large number of objects as high as 10K. We propose a two level hierarchical deep learning architecture inspired by divide & conquer principle that decomposes the large scale recognition architecture into root & leaf level model architectures. Each of the root & leaf level models is trained exclusively to provide superior results than possible by any 1-level deep learning architecture prevalent today. The proposed architecture classifies objects in two steps. In the first step the root level model classifies the object in a high level category. In the second step, the leaf level recognition model for the recognized high level category is selected among all the leaf models. This leaf level model is presented with the same input object image which classifies it in a specific category. Also we propose a blend of leaf level models trained with either supervised or unsupervised learning approaches. Unsupervised learning is suitable whenever labelled data is scarce for the specific leaf level models. Currently the training of leaf level models is in progress; where we have trained 25 out of the total 47 leaf level models as of now. We have trained the leaf models with the best case top-5 error rate of 3.2% on the validation data set for the particular leaf models. Also we demonstrate that the validation error of the leaf level models saturates towards the above mentioned accuracy as the number of epochs are increased to more than sixty.
An Approach to the Analysis of the South Slavic Medieval Labels Using Image Texture
Venue: arXiv cs.CV 2015
Year: 2015

The paper presents a new script classification method for the discrimination of the South Slavic medieval labels. It consists in the textural analysis of the script types. In the first step, each letter is coded by the equivalent script type, which is defined by its typographical features. Obtained coded text is subjected to the run-length statistical analysis and to the adjacent local binary pattern analysis in order to extract the features. The result shows a diversity between the extracted features of the scripts, which makes the feature classification more effective. It is the basis for the classification process of the script identification by using an extension of a state-of-the-art approach for document clustering. The proposed method is evaluated on an example of hand-engraved in stone and hand-printed in paper labels in old Cyrillic, angular and round Glagolitic. Experiments demonstrate very positive results, which prove the effectiveness of the proposed method.
A New Low-Rank Tensor Model for Video Completion
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a new low-rank tensor model based on the circulant algebra, namely, twist tensor nuclear norm or t-TNN for short. The twist tensor denotes a 3-way tensor representation to laterally store 2D data slices in order. On one hand, t-TNN convexly relaxes the tensor multi-rank of the twist tensor in the Fourier domain, which allows an efficient computation using FFT. On the other, t-TNN is equal to the nuclear norm of block circulant matricization of the twist tensor in the original domain, which extends the traditional matrix nuclear norm in a block circulant way. We test the t-TNN model on a video completion application that aims to fill missing values and the experiment results validate its effectiveness, especially when dealing with video recorded by a non-stationary panning camera. The block circulant matricization of the twist tensor can be transformed into a circulant block representation with nuclear norm invariance. This representation, after transformation, exploits the horizontal translation relationship between the frames in a video, and endows the t-TNN model with a more powerful ability to reconstruct panning videos than the existing state-of-the-art low-rank models.
Coupling Analysis Between Twitter and Call Centre
Venue: arXiv cs.SI 2015
Year: 2015

Social media has been contributing many research areas such as data mining, recommender systems, time series analysis, etc. However, there are not many successful applications regarding social media in government agencies. In fact, lots of governments have social media accounts such as twitter and facebook. More and more customers are likely to communicate with governments on social media, causing massive external social media data for governments. This external data would be beneficial for analysing behaviours and real needs of the customers. Besides this, most governments also have a call centre to help customers solve their problems. It is not difficult to imagine that the enquiries on external social media and internal call centre may have some coupling relationships. The couplings could be helpful for studying customers' intent and allocating government's limited resources for better service. In this paper, we mainly focus on analysing the coupling relations between internal call centre and external public media using time series analysis methods for Australia Department of Immigration and Border Protec-tion. The discovered couplings demonstrate that call centre and public media indeed have correlations, which are significant for understanding customers' behaviours.
HEp-2 Cell Classification: The Role of Gaussian Scale Space Theory as A Pre-processing Approach
Venue: arXiv cs.CV 2015
Year: 2015

\textit{Indirect Immunofluorescence Imaging of Human Epithelial Type 2} (HEp-2) cells is an effective way to identify the presence of Anti-Nuclear Antibody (ANA). Most existing works on HEp-2 cell classification mainly focus on feature extraction, feature encoding and classifier design. Very few efforts have been devoted to study the importance of the pre-processing techniques. In this paper, we analyze the importance of the pre-processing, and investigate the role of Gaussian Scale Space (GSS) theory as a pre-processing approach for the HEp-2 cell classification task. We validate the GSS pre-processing under the Local Binary Pattern (LBP) and the Bag-of-Words (BoW) frameworks. Under the BoW framework, the introduced pre-processing approach, using only one Local Orientation Adaptive Descriptor (LOAD), achieved superior performance on the Executable Thematic on Pattern Recognition Techniques for Indirect Immunofluorescence (ET-PRT-IIF) image analysis. Our system, using only one feature, outperformed the winner of the ICPR 2014 contest that combined four types of features. Meanwhile, the proposed pre-processing method is not restricted to this work; it can be generalized to many existing works.
Random Extensive Form Games and its Application to Bargaining
Venue: arXiv cs.GT 2015
Year: 2015

We consider two-player random extensive form games where the payoffs at the leaves are independently drawn uniformly at random from a given feasible set C. We study the asymptotic distribution of the subgame perfect equilibrium outcome for binary-trees with increasing depth in various random (or deterministic) assignments of players to nodes. We characterize the assignments under which the asymptotic distribution concentrates around a point. Our analysis provides a natural way to derive from the asymptotic distribution a novel solution concept for two-player bargaining problems with a solid strategic justification.
Deep Attributes from Context-Aware Regional Neural Codes
Venue: arXiv cs.CV 2015
Year: 2015

Recently, many researches employ middle-layer output of convolutional neural network models (CNN) as features for different visual recognition tasks. Although promising results have been achieved in some empirical studies, such type of representations still suffer from the well-known issue of semantic gap. This paper proposes so-called deep attribute framework to alleviate this issue from three aspects. First, we introduce object region proposals as intermedia to represent target images, and extract features from region proposals. Second, we study aggregating features from different CNN layers for all region proposals. The aggregation yields a holistic yet compact representation of input images. Results show that cross-region max-pooling of soft-max layer output outperform all other layers. As soft-max layer directly corresponds to semantic concepts, this representation is named "deep attributes". Third, we observe that only a small portion of generated regions by object proposals algorithm are correlated to classification target. Therefore, we introduce context-aware region refining algorithm to pick out contextual regions and build context-aware classifiers. We apply the proposed deep attributes framework for various vision tasks. Extensive experiments are conducted on standard benchmarks for three visual recognition tasks, i.e., image classification, fine-grained recognition and visual instance retrieval. Results show that deep attribute approaches achieve state-of-the-art results, and outperforms existing peer methods with a significant margin, even though some benchmarks have little overlap of concepts with the pre-trained CNN models.
Model Checking Embedded C Software using k-Induction and Invariants (extended version)
Venue: arXiv cs.LO 2015
Year: 2015

We present a proof by induction algorithm, which combines k-induction with invariants to model check embedded C software with bounded and unbounded loops. The k-induction algorithm consists of three cases: in the base case, we aim to find a counterexample with up to k loop unwindings; in the forward condition, we check whether loops have been fully unrolled and that the safety property P holds in all states reachable within k unwindings; and in the inductive step, we check that whenever P holds for k unwindings, it also holds after the next unwinding of the system. For each step of the k-induction algorithm, we infer invariants using affine constraints (i.e., polyhedral) to specify pre- and post-conditions. Experimental results show that our approach can handle a wide variety of safety properties in typical embedded software applications from telecommunications, control systems, and medical devices; we demonstrate an improvement of the induction algorithm effectiveness if compared to other approaches.
Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection
Venue: arXiv cs.DS 2015
Year: 2015

We formulate and study a fundamental search and detection problem, Schedule Optimization, motivated by a variety of real-world applications, ranging from monitoring content changes on the web, social networks, and user activities to detecting failure on large systems with many individual machines. We consider a large system consists of many nodes, where each node has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal is to compute a probing schedule that minimizes the expected number of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system. We study the Schedule Optimization problem both for deterministic and randomized memoryless algorithms. We provide lower bounds on the cost of an optimal schedule and construct close to optimal schedules with rigorous mathematical guarantees. Finally, we present an adaptive algorithm that starts with no prior information on the system and converges to the optimal memoryless algorithms by adapting to observed data.
DeepCough: A Deep Convolutional Neural Network in A Wearable Cough Detection System
Venue: arXiv cs.NE 2015
Year: 2015

In this paper, we present a system that employs a wearable acoustic sensor and a deep convolutional neural network for detecting coughs. We evaluate the performance of our system on 14 healthy volunteers and compare it to that of other cough detection systems that have been reported in the literature. Experimental results show that our system achieves a classification sensitivity of 95.1% and a specificity of 99.5%.
Flips and Spanners
Venue: arXiv cs.CG 2015
Year: 2015

In this thesis, we study two different graph problems. The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each pair of points that does not make a large detour. If we achieve this, the resulting graph is called a spanner. We focus our attention on $Θ$-graphs, which are constructed by connecting each point with its nearest neighbour in a fixed number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy on the half-$Θ_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal. In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2n - 33.6$ on the maximum flip distance between any pair of triangulations with n vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $(3n - 9)/5$ flips needed to make a triangulation 4-connected. In addition, we prove tight $Θ(n \log n)$ bounds on the number of flips required in several settings where the edges have unique labels.
Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
Venue: arXiv cs.DC 2015
Year: 2015

The alternating direction method of multipliers (ADMM) has been recognized as a versatile approach for solving modern large-scale machine learning and signal processing problems efficiently. When the data size and/or the problem dimension is large, a distributed version of ADMM can be used, which is capable of distributing the computation load and the data set to a network of computing nodes. Unfortunately, a direct synchronous implementation of such algorithm does not scale well with the problem size, as the algorithm speed is limited by the slowest computing nodes. To address this issue, in a companion paper, we have proposed an asynchronous distributed ADMM (AD-ADMM) and studied its worst-case convergence conditions. In this paper, we further the study by characterizing the conditions under which the AD-ADMM achieves linear convergence. Our conditions as well as the resulting linear rates reveal the impact that various algorithm parameters, network delay and network size have on the algorithm performance. To demonstrate the superior time efficiency of the proposed AD-ADMM, we test the AD-ADMM on a high-performance computer cluster by solving a large-scale logistic regression problem.
Coherent Robust H-Infinity Control of Uncertain Linear Quantum Stochastic Systems
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers a class of uncertain linear quantum systems subject to uncertain perturbations in the system Hamiltonian. We present a method to design a coherent robust H-infinity controller so that the closed loop system is robustly stable and achieves a prescribed level of disturbance attenuation with all the admissible uncertainties. An illustrative example shows that for the given system, the method presented in this paper has improved performance over the existing quantum H-infinity control results without considering uncertainty.
Solving NP-complete problems with delayed signals: an overview of current research directions
Venue: arXiv cs.ET 2015
Year: 2015

In this paper we summarize the existing principles for building unconventional computing devices that involve delayed signals for encoding solutions to NP-complete problems. We are interested in the following aspects: the properties of the signal, the operations performed within the devices, some components required for the physical implementation, precision required for correctly reading the solution and the decrease in the signal's strength. Six problems have been solved so far by using the above enumerated principles: Hamiltonian path, travelling salesman, bounded and unbounded subset sum, Diophantine equations and exact cover. For the hardware implementation several types of signals can be used: light, electric power, sound, electro-magnetic etc.
Equivalence of two Fixed-Point Semantics for Definitional Higher-Order Logic Programs
Venue: arXiv cs.LO 2015
Year: 2015

Two distinct research approaches have been proposed for assigning a purely extensional semantics to higher-order logic programming. The former approach uses classical domain theoretic tools while the latter builds on a fixed-point construction defined on a syntactic instantiation of the source program. The relationships between these two approaches had not been investigated until now. In this paper we demonstrate that for a very broad class of programs, namely the class of definitional programs introduced by W. W. Wadge, the two approaches coincide (with respect to ground atoms that involve symbols of the program). On the other hand, we argue that if existential higher-order variables are allowed to appear in the bodies of program rules, the two approaches are in general different. The results of the paper contribute to a better understanding of the semantics of higher-order logic programming.
Formalizing Termination Proofs under Polynomial Quasi-interpretations
Venue: arXiv cs.LO 2015
Year: 2015

Usual termination proofs for a functional program require to check all the possible reduction paths. Due to an exponential gap between the height and size of such the reduction tree, no naive formalization of termination proofs yields a connection to the polynomial complexity of the given program. We solve this problem employing the notion of minimal function graph, a set of pairs of a term and its normal form, which is defined as the least fixed point of a monotone operator. We show that termination proofs for programs reducing under lexicographic path orders (LPOs for short) and polynomially quasi-interpretable can be optimally performed in a weak fragment of Peano arithmetic. This yields an alternative proof of the fact that every function computed by an LPO-terminating, polynomially quasi-interpretable program is computable in polynomial space. The formalization is indeed optimal since every polynomial-space computable function can be computed by such a program. The crucial observation is that inductive definitions of minimal function graphs under LPO-terminating programs can be approximated with transfinite induction along LPOs.