OpenRaiser/Intern-Atlas huggingface dataset:
Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol
Venue: arXiv cs.DS 2014
Year: 2014

The classical secretary problem investigates the question of how to hire the best secretary from $n$ candidates who come in a uniformly random order. In this work we investigate a parallel generalizations of this problem introduced by Feldman and Tennenholtz [14]. We call it shared $Q$-queue $J$-choice $K$-best secretary problem. In this problem, $n$ candidates are evenly distributed into $Q$ queues, and instead of hiring the best one, the employer wants to hire $J$ candidates among the best $K$ persons. The $J$ quotas are shared by all queues. This problem is a generalized version of $J$-choice $K$-best problem which has been extensively studied and it has more practical value as it characterizes the parallel situation. Although a few of works have been done about this generalization, to the best of our knowledge, no optimal deterministic protocol was known with general $Q$ queues. In this paper, we provide an optimal deterministic protocol for this problem. The protocol is in the same style of the $1\over e$-solution for the classical secretary problem, but with multiple phases and adaptive criteria. Our protocol is very simple and efficient, and we show that several generalizations, such as the fractional $J$-choice $K$-best secretary problem and exclusive $Q$-queue $J$-choice $K$-best secretary problem, can be solved optimally by this protocol with slight modification and the latter one solves an open problem of Feldman and Tennenholtz [14]. In addition, we provide theoretical analysis for two typical cases, including the 1-queue 1-choice $K$-best problem and the shared 2-queue 2-choice 2-best problem. For the former, we prove a lower bound $1-O(\frac{\ln^2K}{K^2})$ of the competitive ratio. For the latter, we show the optimal competitive ratio is $\approx0.372$ while previously the best known result is 0.356 [14].
On the Optimal Solution of Weighted Nuclear Norm Minimization
Venue: arXiv cs.CV 2014
Year: 2014

In recent years, the nuclear norm minimization (NNM) problem has been attracting much attention in computer vision and machine learning. The NNM problem is capitalized on its convexity and it can be solved efficiently. The standard nuclear norm regularizes all singular values equally, which is however not flexible enough to fit real scenarios. Weighted nuclear norm minimization (WNNM) is a natural extension and generalization of NNM. By assigning properly different weights to different singular values, WNNM can lead to state-of-the-art results in applications such as image denoising. Nevertheless, so far the global optimal solution of WNNM problem is not completely solved yet due to its non-convexity in general cases. In this article, we study the theoretical properties of WNNM and prove that WNNM can be equivalently transformed into a quadratic programming problem with linear constraints. This implies that WNNM is equivalent to a convex problem and its global optimum can be readily achieved by off-the-shelf convex optimization solvers. We further show that when the weights are non-descending, the globally optimal solution of WNNM can be obtained in closed-form.
An Integer Programming Formulation of the Minimum Common String Partition problem
Venue: arXiv cs.DM 2014
Year: 2014

We consider the problem of finding a minimum common partition of two strings (MCSP). The problem has its application in genome comparison. MCSP problem is proved to be NP-hard. In this paper, we develop an Integer Programming (IP) formulation for the problem and implement it. The experimental results are compared with the previous state-of-the-art algorithms and are found to be promising.
Comparative analysis of common edge detection techniques in context of object extraction
Venue: arXiv cs.CV 2014
Year: 2014

Edges characterize boundaries and are therefore a problem of practical importance in remote sensing.In this paper a comparative study of various edge detection techniques and band wise analysis of these algorithms in the context of object extraction with regard to remote sensing satellite images from the Indian Remote Sensing Satellite (IRS) sensors LISS 3, LISS 4 and Cartosat1 as well as Google Earth is presented.
Cellular Automata based adaptive resampling technique for the processing of remotely sensed imagery
Venue: arXiv cs.CV 2014
Year: 2014

Resampling techniques are being widely used at different stages of satellite image processing. The existing methodologies cannot perfectly recover features from a completely under sampled image and hence an intelligent adaptive resampling methodology is required. We address these issues and adopt an error metric from the available literature to define interpolation quality. We also propose a new resampling scheme that adapts itself with regard to the pixel and texture variation in the image. The proposed CNN based hybrid method has been found to perform better than the existing methods as it adapts itself with reference to the image features.
Development of the method of computer analogy for studying and solving complex nonlinear systems
Venue: arXiv cs.NA 2014
Year: 2014

A method of representation of a solution as segments of the series in powers of the step of the independent variable is expanded for solving complex systems of ordinary differential equations (ODE): the Lorenz system and other systems. A new procedure of reduction of the representation of the solution to a sum of two parts (regular and random) is performed. A shifting procedure is applied in each level of the independent variable to the random part and it acts as the filter that extracts the values to the regular part. In certain cases it is possible to omit the random part and construct the approximation which does not converge but still provides the qualitative information about the full solution (a linear approximation provides a simple exact solution). Evaluation of the error for this case is performed. Constructing the analytical representation of the solutions for these systems by the developed method is presented.
Jpeg Image Compression Using Discrete Cosine Transform - A Survey
Venue: arXiv cs.MM 2014
Year: 2014

Due to the increasing requirements for transmission of images in computer, mobile environments, the research in the field of image compression has increased significantly. Image compression plays a crucial role in digital image processing, it is also very important for efficient transmission and storage of images. When we compute the number of bits per image resulting from typical sampling rates and quantization methods, we find that Image compression is needed. Therefore development of efficient techniques for image compression has become necessary .This paper is a survey for lossy image compression using Discrete Cosine Transform, it covers JPEG compression algorithm which is used for full-colour still image applications and describes all the components of it.
HVSTO: Efficient Privacy Preserving Hybrid Storage in Cloud Data Center
Venue: arXiv cs.DC 2014
Year: 2014

In cloud data center, shared storage with good management is a main structure used for the storage of virtual machines (VM). In this paper, we proposed Hybrid VM storage (HVSTO), a privacy preserving shared storage system designed for the virtual machine storage in large-scale cloud data center. Unlike traditional shared storage, HVSTO adopts a distributed structure to preserve privacy of virtual machines, which are a threat in traditional centralized structure. To improve the performance of I/O latency in this distributed structure, we use a hybrid system to combine solid state disk and distributed storage. From the evaluation of our demonstration system, HVSTO provides a scalable and sufficient throughput for the platform as a service infrastructure.
Collaborative Driving Support System in Mobile Pervasive Environments
Venue: arXiv cs.NI 2014
Year: 2014

The Bluetooth protocol can be used for intervehicle communication equipped with Bluetooth devices. This work investigates the challenges and feasibility of developing intelligent driving system providing timesensitive information about traffic conditions and roadside facilities. The architecture for collaborative vehicle communication system is presented using the concepts of wireless networks and Bluetooth protocol. We discuss how vehicles can form mobile ad-hoc networks and exchange data by the on-board Bluetooth sensors. The key design concepts of the intelligent driving service infrastructure are analyzed showing collaborative fusion of multiple positional data could give a better understanding of the surrounding traffic conditions for collaborative driving. The technical feasibility of using Bluetooth for data exchange among moving vehicles is evaluated.
Second Life: game, simulator, or serious game?
Venue: arXiv cs.CY 2014
Year: 2014

This article reports on an exploratory case study conducted to examine the viability of Second Life (SL) as an environment for physical simulations and microworlds. It begins by discussing specific features of the SL environment relevant to its use as a support for microworlds and simulations as well as a few differences found between SL and traditional simulators such as Modellus, along with their implications to simulations, as a support for subsequent analysis. Afterwards, we will use Narayanasamy et al. and Johnston and Whitehead criteria to analyze the SL environment and determine into which of training simulators, games, simulation games, or serious games categories SL fits best. We conclude that SL shows itself as a huge and sophisticated simulator of an entire Earthlike world used by thousands of users to simulate real life in some sense and a viable and flexible platform for microworlds and simulations.
A Novel Stochastic Decoding of LDPC Codes with Quantitative Guarantees
Venue: arXiv cs.IT 2014
Year: 2014

Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.
A Performance Model for the Communication in Fast Multipole Methods on HPC Platforms
Venue: arXiv cs.DC 2014
Year: 2014

Exascale systems are predicted to have approximately one billion cores, assuming Gigahertz cores. Limitations on affordable network topologies for distributed memory systems of such massive scale bring new challenges to the current parallel programing model. Currently, there are many efforts to evaluate the hardware and software bottlenecks of exascale designs. There is therefore an urgent need to model application performance and to understand what changes need to be made to ensure extrapolated scalability. The fast multipole method (FMM) was originally developed for accelerating N-body problems in astrophysics and molecular dynamics, but has recently been extended to a wider range of problems, including preconditioners for sparse linear solvers. It's high arithmetic intensity combined with its linear complexity and asynchronous communication patterns makes it a promising algorithm for exascale systems. In this paper, we discuss the challenges for FMM on current parallel computers and future exascale architectures, with a focus on inter-node communication. We develop a performance model that considers the communication patterns of the FMM, and observe a good match between our model and the actual communication time, when latency, bandwidth, network topology, and multi-core penalties are all taken into account. To our knowledge, this is the first formal characterization of inter-node communication in FMM, which validates the model against actual measurements of communication time.
Energy Harvesting Cognitive Radio with Channel-Aware Sensing Strategy
Venue: arXiv cs.IT 2014
Year: 2014

An energy harvesting cognitive radio scenario is considered where a secondary user (SU) with finite battery capacity opportunistically accesses the primary user (PU) channels. The objective is to maximize the throughput of SU under energy neutrality constraint and fading channel conditions in a single-user multi-channel setting. Channel selection criterion based on the probabilistic availability of energy with SU, channel conditions, and primary network's belief state is proposed, which chooses the best subset of channels for sensing, yielding higher throughput. We construct channel-aware optimal and myopic sensing strategies in a Partially Observable Markov Decision Process framework based on the proposed channel selection criterion. The effects of sensing errors and collisions between PU and SU on the throughput of latter are studied. It is shown that there exists a trade-off between the transmission duration and the energy lost in collisions.
Automatic large-scale classification of bird sounds is strongly improved by unsupervised feature learning
Venue: arXiv cs.SD 2014
Year: 2014

Automatic species classification of birds from their sound is a computational tool of increasing importance in ecology, conservation monitoring and vocal communication studies. To make classification useful in practice, it is crucial to improve its accuracy while ensuring that it can run at big data scales. Many approaches use acoustic measures based on spectrogram-type data, such as the Mel-frequency cepstral coefficient (MFCC) features which represent a manually-designed summary of spectral information. However, recent work in machine learning has demonstrated that features learnt automatically from data can often outperform manually-designed feature transforms. Feature learning can be performed at large scale and "unsupervised", meaning it requires no manual data labelling, yet it can improve performance on "supervised" tasks such as classification. In this work we introduce a technique for feature learning from large volumes of bird sound recordings, inspired by techniques that have proven useful in other domains. We experimentally compare twelve different feature representations derived from the Mel spectrum (of which six use this technique), using four large and diverse databases of bird vocalisations, with a random forest classifier. We demonstrate that MFCCs are of limited power in this context, leading to worse performance than the raw Mel spectral data. Conversely, we demonstrate that unsupervised feature learning provides a substantial boost over MFCCs and Mel spectra without adding computational complexity after the model has been trained. The boost is particularly notable for single-label classification tasks at large scale. The spectro-temporal activations learned through our procedure resemble spectro-temporal receptive fields calculated from avian primary auditory forebrain.
Election Attacks with Few Candidates
Venue: arXiv cs.GT 2014
Year: 2014

We investigate the parameterized complexity of strategic behaviors in generalized scoring rules. In particular, we prove that the manipulation, control (all the 22 standard types), and bribery problems are fixed-parameter tractable for most of the generalized scoring rules, with respect to the number of candidates. Our results imply that all these strategic voting problems are fixed-parameter tractable for most of the common voting rules, such as Plurality, r-Approval, Borda, Copeland, Maximin, Bucklin, etc., with respect to the number of candidates.
Allocating Indivisible Resources under Price Rigidities in Polynomial Time
Venue: arXiv cs.GT 2014
Year: 2014

In many realistic problems of allocating resources, economy efficiency must be taken into consideration together with social equality, and price rigidities are often made according to some economic and social needs. We study the computational issues of dynamic mechanisms for selling multiple indivisible items under price rigidities. We propose a polynomial algorithm that can be used to find over-demanded sets of items, and then introduce a dynamic mechanism with rationing to discover constrained Walrasian equilibria under price rigidities in polynomial time. We also address the computation of sellers' expected profits and items' expected prices, and discuss strategical issues in the sense of expected profits.
Density Evolution and Functional Threshold for the Noisy Min-Sum Decoder
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the behavior of the Min-Sum decoder running on noisy devices. The aim is to evaluate the robustness of the decoder in the presence of computation noise, e.g. due to faulty logic in the processing units, which represents a new source of errors that may occur during the decoding process. To this end, we first introduce probabilistic models for the arithmetic and logic units of the the finite-precision Min-Sum decoder, and then carry out the density evolution analysis of the noisy Min-Sum decoder. We show that in some particular cases, the noise introduced by the device can help the Min-Sum decoder to escape from fixed points attractors, and may actually result in an increased correction capacity with respect to the noiseless decoder. We also reveal the existence of a specific threshold phenomenon, referred to as functional threshold. The behavior of the noisy decoder is demonstrated in the asymptotic limit of the code-length -- by using "noisy" density evolution equations -- and it is also verified in the finite-length case by Monte-Carlo simulation.
El egresado de la carrera Ciencias de la Información y su inserción en la gestión de mercadotecnia
Venue: arXiv cs.CY 2014
Year: 2014

The study aims to identify the possibilities offered by academic studies in Cuba for the training of information professionals as marketing managers. A theoretical analysis is conducted of the basic functions of marketing and its information dimension, the specific features of the work of the marketing manager, and the competencies developed by Curriculum D in information science graduates in the Cuban context. Based on the analysis of curricular contents and interviews with ten information professionals working as marketing managers, determination was made of some indispensable competencies which should be developed during the training and later on during service practice.
Hybrid Type-Logical Grammars, First-Order Linear Logic and the Descriptive Inadequacy of Lambda Grammars
Venue: arXiv cs.LO 2014
Year: 2014

In this article we show that hybrid type-logical grammars are a fragment of first-order linear logic. This embedding result has several important consequences: it not only provides a simple new proof theory for the calculus, thereby clarifying the proof-theoretic foundations of hybrid type-logical grammars, but, since the translation is simple and direct, it also provides several new parsing strategies for hybrid type-logical grammars. Second, NP-completeness of hybrid type-logical grammars follows immediately. The main embedding result also sheds new light on problems with lambda grammars/abstract categorial grammars and shows lambda grammars/abstract categorial grammars suffer from problems of over-generation and from problems at the syntax-semantics interface unlike any other categorial grammar.
Decomposition of Diagonal Hermitian Quantum Gates Using Multiple-Controlled Pauli Z Gates
Venue: arXiv cs.ET 2014
Year: 2014

Quantum logic decomposition refers to decomposing a given quantum gate to a set of physically implementable gates. An approach has been presented to decompose arbitrary diagonal quantum gates to a set of multiplexed-rotation gates around z axis. In this paper, a special class of diagonal quantum gates, namely diagonal Hermitian quantum gates, is considered and a new perspective to the decomposition problem with respect to decomposing these gates is presented. It is first shown that these gates can be decomposed to a set that solely consists of multiple-controlled Z gates. Then a binary representation for the diagonal Hermitian gates is introduced. It is shown that the binary representations of multiple-controlled Z gates form a basis for the vector space that is produced by the binary representations of all diagonal Hermitian quantum gates. Moreover, the problem of decomposing a given diagonal Hermitian gate is mapped to the problem of writing its binary representation in the specific basis mentioned above. Moreover, CZ gate is suggested to be the two-qubit gate in the decomposition library, instead of previously used CNOT gate. Experimental results show that the proposed approach can lead to circuits with lower costs in comparison with the previous ones.
Model Predictive Frequency Control Employing Stability Constraints
Venue: arXiv cs.SY 2014
Year: 2014

In this article a model predictive control (MPC) based frequency control scheme for energy storage units was derived, focusing on the incorporation of stability constraints based on Lyapunov theory and the concept of passivity. The proposed control schemes, guaranteeing closed-loop stability, are applied on a one-area and two-area power system. For the two-area power system, a coordinated (centralized) control and an uncoordinated (decentralized) control approach is conducted. The stability properties of the different MPC setups were derived, implemented and simulated. Furthermore the corresponding control performance was analyzed.
Optimal Algorithms for $L_1$-subspace Signal Processing
Venue: arXiv cs.DS 2014
Year: 2014

We describe ways to define and calculate $L_1$-norm signal subspaces which are less sensitive to outlying data than $L_2$-calculated subspaces. We start with the computation of the $L_1$ maximum-projection principal component of a data matrix containing $N$ signal samples of dimension $D$. We show that while the general problem is formally NP-hard in asymptotically large $N$, $D$, the case of engineering interest of fixed dimension $D$ and asymptotically large sample size $N$ is not. In particular, for the case where the sample size is less than the fixed dimension ($N<D$), we present in explicit form an optimal algorithm of computational cost $2^N$. For the case $N \geq D$, we present an optimal algorithm of complexity $\mathcal O(N^D)$. We generalize to multiple $L_1$-max-projection components and present an explicit optimal $L_1$ subspace calculation algorithm of complexity $\mathcal O(N^{DK-K+1})$ where $K$ is the desired number of $L_1$ principal components (subspace rank). We conclude with illustrations of $L_1$-subspace signal processing in the fields of data dimensionality reduction, direction-of-arrival estimation, and image conditioning/restoration.