OpenRaiser/Intern-Atlas huggingface dataset:
Single machine scheduling problems with uncertain parameters and the OWA criterion
Venue: arXiv cs.DS 2014
Year: 2014

In this paper a class of single machine scheduling problems is discussed. It is assumed that job parameters, such as processing times, due dates, or weights are uncertain and their values are specified in the form of a discrete scenario set. The Ordered Weighted Averaging (OWA) aggregation operator is used to choose an optimal schedule. The OWA operator generalizes traditional criteria in decision making under uncertainty, such as the maximum, average, median or Hurwicz criterion. It also allows us to extend the robust approach to scheduling by taking into account various attitudes of decision makers towards the risk. In this paper a general framework for solving single machine scheduling problems with the OWA criterion is proposed and some positive and negative computational results for two basic single machine scheduling problems are provided.
Iterative Non-Local Shrinkage Algorithm for MR Image Reconstruction
Venue: arXiv cs.CV 2014
Year: 2014

We introduce a fast iterative non-local shrinkage algorithm to recover MRI data from undersampled Fourier measurements. This approach is enabled by the reformulation of current non-local schemes as an alternating algorithm to minimize a global criterion. The proposed algorithm alternates between a non-local shrinkage step and a quadratic subproblem. We derive analytical shrinkage rules for several penalties that are relevant in non-local regularization. The redundancy in the searches used to evaluate the shrinkage steps are exploited using filtering operations. The resulting algorithm is observed to be considerably faster than current alternating non-local algorithms. The comparisons of the proposed scheme with state-of-the-art regularization schemes show a considerable reduction in alias artifacts and preservation of edges.
Real-Time Predictive Modeling and Robust Avoidance of Pedestrians with Uncertain, Changing Intentions
Venue: arXiv cs.RO 2014
Year: 2014

To plan safe trajectories in urban environments, autonomous vehicles must be able to quickly assess the future intentions of dynamic agents. Pedestrians are particularly challenging to model, as their motion patterns are often uncertain and/or unknown a priori. This paper presents a novel changepoint detection and clustering algorithm that, when coupled with offline unsupervised learning of a Gaussian process mixture model (DPGP), enables quick detection of changes in intent and online learning of motion patterns not seen in prior training data. The resulting long-term movement predictions demonstrate improved accuracy relative to offline learning alone, in terms of both intent and trajectory prediction. By embedding these predictions within a chance-constrained motion planner, trajectories which are probabilistically safe to pedestrian motions can be identified in real-time. Hardware experiments demonstrate that this approach can accurately predict pedestrian motion patterns from onboard sensor/perception data and facilitate robust navigation within a dynamic environment.
Decision Problems for Deterministic Pushdown Automata on Infinite Words
Venue: arXiv cs.FL 2014
Year: 2014

The article surveys some decidability results for DPDAs on infinite words (omega-DPDA). We summarize some recent results on the decidability of the regularity and the equivalence problem for the class of weak omega-DPDAs. Furthermore, we present some new results on the parity index problem for omega-DPDAs. For the specification of a parity condition, the states of the omega-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given omega-DPDA. We provide some decidability results on variations of this question for some classes of omega-DPDAs.
Simplifying Nondeterministic Finite Cover Automata
Venue: arXiv cs.FL 2014
Year: 2014

The concept of Deterministic Finite Cover Automata (DFCA) was introduced at WIA '98, as a more compact representation than Deterministic Finite Automata (DFA) for finite languages. In some cases representing a finite language, Nondeterministic Finite Automata (NFA) may significantly reduce the number of states used. The combined power of the succinctness of the representation of finite languages using both cover languages and non-determinism has been suggested, but never systematically studied. In the present paper, for nondeterministic finite cover automata (NFCA) and l-nondeterministic finite cover automaton (l-NFCA), we show that minimization can be as hard as minimizing NFAs for regular languages, even in the case of NFCAs using unary alphabets. Moreover, we show how we can adapt the methods used to reduce, or minimize the size of NFAs/DFCAs/l-DFCAs, for simplifying NFCAs/l-NFCAs.
Compressive Phase Retrieval via Generalized Approximate Message Passing
Venue: arXiv cs.IT 2014
Year: 2014

In phase retrieval, the goal is to recover a signal $\mathbf{x}\in\mathbb{C}^N$ from the magnitudes of linear measurements $\mathbf{Ax}\in\mathbb{C}^M$. While recent theory has established that $M\approx 4N$ intensity measurements are necessary and sufficient to recover generic $\mathbf{x}$, there is great interest in reducing the number of measurements through the exploitation of sparse $\mathbf{x}$, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. Our experiments suggest that approximately $M\geq 2K\log_2(N/K)$ intensity measurements suffice to recover $K$-sparse Bernoulli-Gaussian signals for $\mathbf{A}$ with i.i.d Gaussian entries and $K\ll N$. Meanwhile, when recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements at 30~dB measurement SNR, PR-GAMP achieved an output SNR of no less than 28~dB in all of 100 random trials, with a median runtime of only 7.3 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, our experiments suggest that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the sparsity and problem dimensions increase.
Application of Lossless Data Compression Techniques to Radio Astronomy Data flows
Venue: arXiv cs.IT 2014
Year: 2014

The modern practice of Radio Astronomy is characterized by extremes of data volume and rates, principally because of the direct relationship between the signal to noise ratio that can be achieved and the need to Nyquist sample the RF bandwidth necessary by way of support. The transport of these data flows is costly. By examining the statistical nature of typical data flows and applying well known techniques from the field of Information Theory the following work shows that lossless compression of typical radio astronomy data flows is in theory possible. The key parameter in determining the degree of compression possible is the standard deviation of the data. The practical application of compression could prove beneficial in reducing the costs of data transport and (arguably) storage for new generation instruments such as the Square Kilometer Array.
Efficient Hybrid Inline and Out-of-line Deduplication for Backup Storage
Venue: arXiv cs.DC 2014
Year: 2014

Backup storage systems often remove redundancy across backups via inline deduplication, which works by referring duplicate chunks of the latest backup to those of existing backups. However, inline deduplication degrades restore performance of the latest backup due to fragmentation, and complicates deletion of ex- pired backups due to the sharing of data chunks. While out-of-line deduplication addresses the problems by forward-pointing existing duplicate chunks to those of the latest backup, it introduces additional I/Os of writing and removing duplicate chunks. We design and implement RevDedup, an efficient hybrid inline and out-of-line deduplication system for backup storage. It applies coarse-grained inline deduplication to remove duplicates of the latest backup, and then fine-grained out-of-line reverse deduplication to remove duplicates from older backups. Our reverse deduplication design limits the I/O overhead and prepares for efficient deletion of expired backups. Through extensive testbed experiments using synthetic and real-world datasets, we show that RevDedup can bring high performance to the backup, restore, and deletion operations, while maintaining high storage efficiency comparable to conventional inline deduplication.
A Logical Formalization of a Secure XML Database
Venue: arXiv cs.DB 2014
Year: 2014

In this paper, we first define a logical theory representing an XML database supporting XPath as query language and XUpdate as modification language. We then extend our theory with predicates allowing us to specify the security policy protecting the database. The security policy includes rules addressing the read and write privileges. We propose axioms to derive the database view each user is permitted to see. We also propose axioms to derive the new database content after an update.
Joint Spectrum and Power Allocation for Multi-node Cooperative Wireless Systems
Venue: arXiv cs.IT 2014
Year: 2014

Energy efficiency is a growing concern for wireless networks, not only due to the emerging traffic demand from smart devices, but also because of the dependence on the traditional unsustainable energy and the overall environmental concerns. The urgent call for reducing power consumption while meeting system requirements has motivated increasing research efforts on green radio. In this paper, we investigate a new joint spectrum and power allocation scheme for a cooperative downlink multi-user system using the frequency division multiple access scheme, in which arbitrary M base stations (BSs) coordinately allocate their resources to each user equipment (UE). With the assumption that multi-BS UE (user being served by multi-BS) would require the same amount of spectrum from these BSs, we conclude that when the number of multi-BS UEs is limited by M-1, the resource allocation scheme can always guarantee the minimum overall transmit power consumption while meeting the throughput requirement of each UE and also each BS's power constraint. Then, to decide the clusters of multi-BS UEs and the clusters of individual-BS UEs (users being served by individual BSs), we propose a UE-BS association scheme and a complexity reduction scheme. Finally, a novel joint spectrum and power allocation algorithm is proposed to minimize the total power consumption. Simulation results are presented to verify the optimality of the derived schemes.
Self-tuned Visual Subclass Learning with Shared Samples An Incremental Approach
Venue: arXiv cs.CV 2014
Year: 2014

Computer vision tasks are traditionally defined and evaluated using semantic categories. However, it is known to the field that semantic classes do not necessarily correspond to a unique visual class (e.g. inside and outside of a car). Furthermore, many of the feasible learning techniques at hand cannot model a visual class which appears consistent to the human eye. These problems have motivated the use of 1) Unsupervised or supervised clustering as a preprocessing step to identify the visual subclasses to be used in a mixture-of-experts learning regime. 2) Felzenszwalb et al. part model and other works model mixture assignment with latent variables which is optimized during learning 3) Highly non-linear classifiers which are inherently capable of modelling multi-modal input space but are inefficient at the test time. In this work, we promote an incremental view over the recognition of semantic classes with varied appearances. We propose an optimization technique which incrementally finds maximal visual subclasses in a regularized risk minimization framework. Our proposed approach unifies the clustering and classification steps in a single algorithm. The importance of this approach is its compliance with the classification via the fact that it does not need to know about the number of clusters, the representation and similarity measures used in pre-processing clustering methods a priori. Following this approach we show both qualitatively and quantitatively significant results. We show that the visual subclasses demonstrate a long tail distribution. Finally, we show that state of the art object detection methods (e.g. DPM) are unable to use the tails of this distribution comprising 50\% of the training samples. In fact we show that DPM performance slightly increases on average by the removal of this half of the data.
Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
Venue: arXiv cs.DM 2014
Year: 2014

This paper describes a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, we obtain that the 29-comparator network found by Waksman in 1969 is optimal when sorting ten inputs. This closes the two smallest open instances of the optimal size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to eight inputs. The proof involves a combination of two methodologies: one based on exploiting the abundance of symmetries in sorting networks, and the other, based on an encoding of the problem to that of satisfiability of propositional logic. We illustrate that, while each of these can single handed solve smaller instances of the problem, it is their combination which leads to an efficient solution for nine inputs.
Optimal Cooperative Power Allocation for Energy Harvesting Enabled Relay Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we present a new power allocation scheme for a decode-and-forward (DF) relaying-enhanced cooperative wireless system. While both source and relay nodes may have limited traditional brown power supply or fixed green energy storage, the hybrid source node can also draw power from the surrounding radio frequency (RF) signals. In particular, we assume a deterministic RF energy harvesting (EH) model under which the signals transmitted by the relay serve as the renewable energy source for the source node. The amount of harvested energy is known for a given transmission power of the forwarding signal and channel condition between the source and relay nodes. To maximize the overall throughput while meeting the constraints imposed by the non-sustainable energy sources and the renewable energy source, an optimization problem is formulated and solved. Based on different harvesting efficiency and channel condition, closed form solutions are derived to obtain the optimal source and relay power allocation jointly. It is shown that instead of demanding high on-grid power supply or high green energy availability, the system can achieve compatible or higher throughput by utilizing the harvested energy.
Node Classification in Uncertain Graphs
Venue: arXiv cs.DB 2014
Year: 2014

In many real applications that use and analyze networked data, the links in the network graph may be erroneous, or derived from probabilistic techniques. In such cases, the node classification problem can be challenging, since the unreliability of the links may affect the final results of the classification process. If the information about link reliability is not used explicitly, the classification accuracy in the underlying network may be affected adversely. In this paper, we focus on situations that require the analysis of the uncertainty that is present in the graph structure. We study the novel problem of node classification in uncertain graphs, by treating uncertainty as a first-class citizen. We propose two techniques based on a Bayes model and automatic parameter selection, and show that the incorporation of uncertainty in the classification process as a first-class citizen is beneficial. We experimentally evaluate the proposed approach using different real data sets, and study the behavior of the algorithms under different conditions. The results demonstrate the effectiveness and efficiency of our approach.
Computerization of African languages-French dictionaries
Venue: arXiv cs.CL 2014
Year: 2014

This paper relates work done during the DiLAF project. It consists in converting 5 bilingual African language-French dictionaries originally in Word format into XML following the LMF model. The languages processed are Bambara, Hausa, Kanuri, Tamajaq and Songhai-zarma, still considered as under-resourced languages concerning Natural Language Processing tools. Once converted, the dictionaries are available online on the Jibiki platform for lookup and modification. The DiLAF project is first presented. A description of each dictionary follows. Then, the conversion methodology from .doc format to XML files is presented. A specific point on the usage of Unicode follows. Then, each step of the conversion into XML and LMF is detailed. The last part presents the Jibiki lexical resources management platform used for the project.
Impossibility of Gathering, a Certification
Venue: arXiv cs.LO 2014
Year: 2014

Recent advances in Distributed Computing highlight models and algorithms for autonomous swarms of mobile robots that self-organise and cooperate to solve global objectives. The overwhelming majority of works so far considers handmade algorithms and proofs of correctness. This paper builds upon a previously proposed formal framework to certify the correctness of impossibility results regarding distributed algorithms that are dedicated to autonomous mobile robots evolving in a continuous space. As a case study, we consider the problem of gathering all robots at a particular location, not known beforehand. A fundamental (but not yet formally certified) result, due to Suzuki and Yamashita, states that this simple task is impossible for two robots executing deterministic code and initially located at distinct positions. Not only do we obtain a certified proof of the original impossibility result, we also get the more general impossibility of gathering with an even number of robots, when any two robots are possibly initially at the same exact location.
Modeling and Nonlinear Control of Gantry Crane Using Feedback Linearization Method
Venue: arXiv cs.SY 2014
Year: 2014

Due to the requirements of high positioning accuracy, small swing angle, short transportation time, and high safety, both motion and stabilization control for an gantry crane system becomes an interesting issue in the field of control technology development. In this paper, dynamic model of gantry crane is extracted using Lagrange method. This model has been linearized and weaknesses of state feedback control of this model is reviewed. To solve these problems, state feedback gain matrix is calculated using LQR method and results are fully investigated. Finally, a full nonlinear solution of problem using feedback linearization method is implemented and results are compared with previous works.
Minimum data rate for stabilization of linear systems with parametric uncertainties
Venue: arXiv cs.SY 2014
Year: 2014

We study a stabilization problem of linear uncertain systems with parametric uncertainties via feedback control over data-rate-constrained channels. The objective is to find the limitation on the amount of information that must be conveyed through the channels for achieving stabilization and in particular how the plant uncertainties affect it. We derive a necessary condition and a sufficient condition for stabilizing the closed-loop system. These conditions provide limitations in the form of bounds on data rate and magnitude of uncertainty on plant parameters. The bounds are characterized by the product of the poles of the nominal plant and are less conservative than those known in the literature. In the course of deriving these results, a new class of nonuniform quantizers is found to be effective in reducing the required data rate. For scalar plants, these quantizers are shown to minimize the required data rate, and the obtained conditions become tight.
Building of Networks of Natural Hierarchies of Terms Based on Analysis of Texts Corpora
Venue: arXiv cs.CL 2014
Year: 2014

The technique of building of networks of hierarchies of terms based on the analysis of chosen text corpora is offered. The technique is based on the methodology of horizontal visibility graphs. Constructed and investigated language network, formed on the basis of electronic preprints arXiv on topics of information retrieval.
Ancilla-Quantum Cost Trade-off during Reversible Logic Synthesis using Exclusive Sum-of-Products
Venue: arXiv cs.ET 2014
Year: 2014

Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.
Evaluating the fully automatic multi-language translation of the Swiss avalanche bulletin
Venue: arXiv cs.CL 2014
Year: 2014

The Swiss avalanche bulletin is produced twice a day in four languages. Due to the lack of time available for manual translation, a fully automated translation system is employed, based on a catalogue of predefined phrases and predetermined rules of how these phrases can be combined to produce sentences. The system is able to automatically translate such sentences from German into the target languages French, Italian and English without subsequent proofreading or correction. Our catalogue of phrases is limited to a small sublanguage. The reduction of daily translation costs is expected to offset the initial development costs within a few years. After being operational for two winter seasons, we assess here the quality of the produced texts based on an evaluation where participants rate real danger descriptions from both origins, the catalogue of phrases versus the manually written and translated texts. With a mean recognition rate of 55%, users can hardly distinguish between the two types of texts, and give similar ratings with respect to their language quality. Overall, the output from the catalogue system can be considered virtually equivalent to a text written by avalanche forecasters and then manually translated by professional translators. Furthermore, forecasters declared that all relevant situations were captured by the system with sufficient accuracy and within the limited time available.