OpenRaiser/Intern-Atlas huggingface dataset:
Designing Electronic Markets for Defeasible-based Contractual Agents
Venue: arXiv cs.MA 2013
Year: 2013

The design of punishment policies applied to specific domains linking agents actions to material penalties is an open research issue. The proposed framework applies principles of contract law to set penalties: expectation damages, opportunity cost, reliance damages, and party design remedies. In order to decide which remedy provides maximum welfare within an electronic market, a simulation environment called DEMCA (Designing Electronic Markets for Contractual Agents) was developed. Knowledge representation and the reasoning capabilities of the agents are based on an extended version of temporal defeasible logic.
Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
Venue: arXiv cs.SY 2013
Year: 2013

Various distributed optimization methods have been developed for solving problems which have simple local constraint sets and whose objective function is the sum of local cost functions of distributed agents in a network. Motivated by emerging applications in smart grid and distributed sparse regression, this paper studies distributed optimization methods for solving general problems which have a coupled global cost function and have inequality constraints. We consider a network scenario where each agent has no global knowledge and can access only its local mapping and constraint functions. To solve this problem in a distributed manner, we propose a consensus-based distributed primal-dual perturbation (PDP) algorithm. In the algorithm, agents employ the average consensus technique to estimate the global cost and constraint functions via exchanging messages with neighbors, and meanwhile use a local primal-dual perturbed subgradient method to approach a global optimum. The proposed PDP method not only can handle smooth inequality constraints but also non-smooth constraints such as some sparsity promoting constraints arising in sparse optimization. We prove that the proposed PDP algorithm converges to an optimal primal-dual solution of the original problem, under standard problem and network assumptions. Numerical results illustrating the performance of the proposed algorithm for a distributed demand response control problem in smart grid are also presented.
Bisimulation-Based Comparisons for Interpretations in Description Logics
Venue: arXiv cs.LO 2013
Year: 2013

We study comparisons between interpretations in description logics with respect to "logical consequences" of the form of semi-positive concepts (like semi-positive concept assertions). Such comparisons are characterized by conditions similar to the ones of bisimulations. The simplest among the considered logics is a variant of PDL (propositional dynamic logic). The others extend that logic with inverse roles, nominals, quantified number restrictions, the universal role, and/or the concept constructor for expressing the local reflexivity of a role. The studied problems are: preservation of semi-positive concepts with respect to comparisons, the Hennessy-Milner property for comparisons, and minimization of interpretations that preserves semi-positive concepts.
Online Makespan Minimization with Parallel Schedules
Venue: arXiv cs.DS 2013
Year: 2013

In online makespan minimization a sequence of jobs $σ= J_1,..., J_n$ has to be scheduled on $m$ identical parallel machines so as to minimize the maximum completion time of any job. We investigate the problem with an essentially new model of resource augmentation. Here, an online algorithm is allowed to build several schedules in parallel while processing $σ$. At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. We develop a $(4/3+\eps)$-competitive algorithm, for any $0<\eps\leq 1$, that uses a number of $1/\eps^{O(\log (1/\eps))}$ schedules. We also give a $(1+\eps)$-competitive algorithm, for any $0<\eps\leq 1$, that builds a polynomial number of $(m/\eps)^{O(\log (1/\eps) / \eps)}$ schedules. This value depends on $m$ but is independent of the input $σ$. The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4/3 must construct $Ω(m)$ schedules. Our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of a job sequence $σ$ to within a factor of $1+\eps$ and (2) guess the job processing times and their frequencies in $σ$. In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant. The competitive ratios achieved using parallel schedules are considerably smaller than those in the standard problem without resource augmentation.
Guiding Blind Transmitters: Degrees of Freedom Optimal Interference Alignment Using Relays
Venue: arXiv cs.IT 2013
Year: 2013

Channel state information (CSI) at the transmitters (CSIT) is of importance for interference alignment schemes to achieve the optimal degrees of freedom (DoF) for wireless networks. This paper investigates the impact of half-duplex relays on the degrees of freedom (DoF) of the X channel and the interference channel when the transmitters are blind in the sense that no ISIT is available. In particular, it is shown that adding relay nodes with global CSI to the communication model is sufficient to recover the DoF that is the optimal for these models with global CSI at the transmitters. The relay nodes in essence help steer the directions of the transmitted signals to facilitate interference alignment to achieve the optimal DoF with CSIT. The general MxN X channel with relays and the K-user interference channel are both investigated, and sufficient conditions on the number of antennas at the relays and the number of relays needed to achieve the optimal DoF with CSIT are established. Using relays, the optimal DoF can be achieved in finite channel uses. The DoF for the case when relays only have delayed CSI is also investigated, and it is shown that with delayed CSI at the relay the optimal DoF with full CSIT cannot be achieved. Special cases of the X channel and interference channel are investigated to obtain further design insights.
A novice looks at emotional cognition
Venue: arXiv cs.AI 2013
Year: 2013

Modeling emotional-cognition is in a nascent stage and therefore wide-open for new ideas and discussions. In this paper the author looks at the modeling problem by bringing in ideas from axiomatic mathematics, information theory, computer science, molecular biology, non-linear dynamical systems and quantum computing and explains how ideas from these disciplines may have applications in modeling emotional-cognition.
Policy Aware Geospatial Data
Venue: arXiv cs.OH 2013
Year: 2013

Digital Rights Management (DRM) prevents end-users from using content in a manner inconsistent with its creator's wishes. The license describing these use-conditions typically accompanies the content as its metadata. A resulting problem is that the license and the content can get separated and lose track of each other. The best metadata have two distinct qualities--they are created automatically without user intervention, and they are embedded within the data that they describe. If licenses are also created and transported this way, data will always have licenses, and the licenses will be readily examinable. When two or more datasets are combined, a new dataset, and with it a new license, are created. This new license is a function of the licenses of the component datasets and any additional conditions that the person combining the datasets might want to impose. Following the notion of a data-purpose algebra, we model this phenomenon by interpreting the transfer and conjunction of data as inducing an algebraic operation on the corresponding licenses. When a dataset passes from one source to the next its license is transformed in a deterministic way, and similarly when datasets are combined the associated licenses are combined in a non-trivial algebraic manner. Modern, computer-savvy, licensing regimes such as Creative Commons allow writing the license in a special kind of language called Creative Commons Rights Expression Language (ccREL). ccREL allows creating and embedding the license using RDFa utilizing XHTML. This is preferred over DRM which includes the rights in a binary file completely opaque to nearly all users. The colocation of metadata with human-visible XHTML makes the license more transparent. In this paper we describe a methodology for creating and embedding licenses in geographic data utilizing ccREL, and programmatically examining embedded licenses in component data...
An Efficient MAC Protocol with Selective Grouping and Cooperative Sensing in Cognitive Radio Networks
Venue: arXiv cs.ET 2013
Year: 2013

In cognitive radio networks, spectrum sensing is a crucial technique to discover spectrum opportunities for the Secondary Users (SUs). The quality of spectrum sensing is evaluated by both sensing accuracy and sensing efficiency. Here, sensing accuracy is represented by the false alarm probability and the detection probability while sensing efficiency is represented by the sensing overhead and network throughput. In this paper, we propose a group-based cooperative Medium Access Control (MAC) protocol called GC-MAC, which addresses the tradeoff between sensing accuracy and efficiency. In GC-MAC, the cooperative SUs are grouped into several teams. During a sensing period, each team senses a different channel while SUs in the same team perform the joint detection on the targeted channel. The sensing process will not stop unless an available channel is discovered. To reduce the sensing overhead, an SU-selecting algorithm is presented to selectively choose the cooperative SUs based on the channel dynamics and usage patterns. Then, an analytical model is built to study the sensing accuracy-efficiency tradeoff under two types of channel conditions: time-invariant channel and time-varying channel. An optimization problem that maximizes achievable throughput is formulated to optimize the important design parameters. Both saturation and non-saturation situations are investigated with respect to throughput and sensing overhead. Simulation results indicate that the proposed protocol is able to significantly decrease sensing overhead and increase network throughput with guaranteed sensing accuracy.
Chain minors are FPT
Venue: arXiv cs.DS 2013
Year: 2013

Given two finite posets P and Q, P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C_Q in Q with the property that f restricted to C_Q is an isomorphism of chains. We give an algorithm to decide whether a poset P is a chain minor of o poset Q that runs in time O(|Q| log |Q|) for every fixed poset P. This solves an open problem from the monograph by Downey and Fellows [Parameterized Complexity, 1999] who asked whether the problem was fixed parameter tractable.
Approximation Algorithms for Vehicle Routing Problems with Stochastic Demands on Trees
Venue: arXiv cs.DS 2013
Year: 2013

We consider the vehicle routing problem with stochastic demands (VRPSD) on tree structured networks with a single depot. The problem we are concerned with in this paper is to find a set of tours for the vehicle with minimum expected length. Every tour begins at the depot, visits a subset of customers and returns to the depot without violating the capacity constraint. Randomized approximation algorithm achieving approximation guarantees of 2 for split-delivery VRPSD, and 3 for un-split delivery VRPSD are obtained.
Paging with dynamic memory capacity
Venue: arXiv cs.DS 2013
Year: 2013

We study a generalization of the classic paging problem that allows the amount of available memory to vary over time - capturing a fundamental property of many modern computing realities, from cloud computing to multi-core and energy-optimized processors. It turns out that good performance in the "classic" case provides no performance guarantees when memory capacity fluctuates: roughly speaking, moving from static to dynamic capacity can mean the difference between optimality within a factor 2 in space and time, and suboptimality by an arbitrarily large factor. More precisely, adopting the competitive analysis framework, we show that some online paging algorithms, despite having an optimal (h,k)-competitive ratio when capacity remains constant, are not (3,k)-competitive for any arbitrarily large k in the presence of minimal capacity fluctuations. In this light it is surprising that several classic paging algorithms perform remarkably well even if memory capacity changes adversarially - even without taking those changes into explicit account! In particular, we prove that LFD still achieves the minimum number of faults, and that several classic online algorithms such as LRU have a "dynamic" (h,k)-competitive ratio that is the best one can achieve without knowledge of future page requests, even if one had perfect knowledge of future capacity fluctuations (an exact characterization of this ratio shows it is almost, albeit not quite, equal to the "classic" ratio k/(k-h+1)). In other words, with careful management, knowing/predicting future memory resources appears far less crucial to performance than knowing/predicting future data accesses.
Spaces, Trees and Colors: The Algorithmic Landscape of Document Retrieval on Sequences
Venue: arXiv cs.IR 2013
Year: 2013

Document retrieval is one of the best established information retrieval activities since the sixties, pervading all search engines. Its aim is to obtain, from a collection of text documents, those most relevant to a pattern query. Current technology is mostly oriented to "natural language" text collections, where inverted indices are the preferred solution. As successful as this paradigm has been, it fails to properly handle some East Asian languages and other scenarios where the "natural language" assumptions do not hold. In this survey we cover the recent research in extending the document retrieval techniques to a broader class of sequence collections, which has applications bioinformatics, data and Web mining, chemoinformatics, software engineering, multimedia information retrieval, and many others. We focus on the algorithmic aspects of the techniques, uncovering a rich world of relations between document retrieval challenges and fundamental problems on trees, strings, range queries, discrete geometry, and others.
Displacement Convexity, A Useful Framework for the Study of Spatially Coupled Codes
Venue: arXiv cs.IT 2013
Year: 2013

Spatial coupling has recently emerged as a powerful paradigm to construct graphical models that work well under low-complexity message-passing algorithms. Although much progress has been made on the analysis of spatially coupled models under message passing, there is still room for improvement, both in terms of simplifying existing proofs as well as in terms of proving additional properties. We introduce one further tool for the analysis, namely the concept of displacement convexity. This concept plays a crucial role in the theory of optimal transport and, quite remarkably, it is also well suited for the analysis of spatially coupled systems. In cases where the concept applies, displacement convexity allows functionals of distributions which are not convex in the usual sense to be represented in an alternative form, so that they are convex with respect to the new parametrization. As a proof of concept we consider spatially coupled $(l,r)$-regular Gallager ensembles when transmission takes place over the binary erasure channel. We show that the potential function of the coupled system is displacement convex. Due to possible translational degrees of freedom convexity by itself falls short of establishing the uniqueness of the minimizing profile. For the spatially coupled $(l,r)$-regular system strict displacement convexity holds when a global translation degree of freedom is removed. Implications for the uniqueness of the minimizer and for solutions of the density evolution equation are discussed.
Polynomial Systems Solving by Fast Linear Algebra
Venue: arXiv cs.SC 2013
Year: 2013

Polynomial system solving is a classical problem in mathematics with a wide range of applications. This makes its complexity a fundamental problem in computer science. Depending on the context, solving has different meanings. In order to stick to the most general case, we consider a representation of the solutions from which one can easily recover the exact solutions or a certified approximation of them. Under generic assumption, such a representation is given by the lexicographical Gröbner basis of the system and consists of a set of univariate polynomials. The best known algorithm for computing the lexicographical Gröbner basis is in $\widetilde{O}(d^{3n})$ arithmetic operations where $n$ is the number of variables and $d$ is the maximal degree of the equations in the input system. The notation $\widetilde{O}$ means that we neglect polynomial factors in $n$. We show that this complexity can be decreased to $\widetilde{O}(d^{ωn})$ where $2 \leq ω< 2.3727$ is the exponent in the complexity of multiplying two dense matrices. Consequently, when the input polynomial system is either generic or reaches the Bézout bound, the complexity of solving a polynomial system is decreased from $\widetilde{O}(D^3)$ to $\widetilde{O}(D^ω)$ where $D$ is the number of solutions of the system. To achieve this result we propose new algorithms which rely on fast linear algebra. When the degree of the equations are bounded uniformly by a constant we propose a deterministic algorithm. In the unbounded case we present a Las Vegas algorithm.
Two-Unicast Two-Hop Interference Network: Finite-Field Model
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we present a novel framework to convert the $K$-user multiple access channel (MAC) over $\FF_{p^m}$ into the $K$-user MAC over ground field $\FF_{p}$ with $m$ multiple inputs/outputs (MIMO). This framework makes it possible to develop coding schemes for MIMO channel as done in symbol extension for time-varying channel. Using aligned network diagonalization based on this framework, we show that the sum-rate of $(2m-1)\log{p}$ is achievable for a $2\times 2\times 2$ interference channel over $\FF_{p^m}$. We also provide some relation between field extension and symbol extension.
An Auction Mechanism for Resource Allocation in Mobile Cloud Computing Systems
Venue: arXiv cs.DC 2013
Year: 2013

A mobile cloud computing system is composed of heterogeneous services and resources to be allocated by the cloud service provider to mobile cloud users. On one hand, some of these resources are substitutable (e.g., users can use storage from different places) that they have similar functions to the users. On the other hand, some resources are complementary that the user will need them as a bundle (e.g., users need both wireless connection and storage for online photo posting). In this paper, we first model the resource allocation process of a mobile cloud computing system as an auction mechanism with premium and discount factors. The premium and discount factors indicate complementary and substitutable relations among cloud resources provided by the service provider. Then, we analyze the individual rationality and incentive compatibility (truthfulness) properties of the users in the proposed auction mechanism. The optimal solutions of the resource allocation and cost charging schemes in the auction mechanism is discussed afterwards.
A Two-Phase Maximum-Likelihood Sequence Estimation for Receivers with Partial CSI
Venue: arXiv cs.IT 2013
Year: 2013

The optimality of the conventional maximum likelihood sequence estimation (MLSE), also known as the Viterbi Algorithm (VA), relies on the assumption that the receiver has perfect knowledge of the channel coefficients or channel state information (CSI). However, in practical situations that fail the assumption, the MLSE method becomes suboptimal and then exhaustive checking is the only way to obtain the ML sequence. At this background, considering directly the ML criterion for partial CSI, we propose a two-phase low-complexity MLSE algorithm, in which the first phase performs the conventional MLSE algorithm in order to retain necessary information for the backward VA performed in the second phase. Simulations show that when the training sequence is moderately long in comparison with the entire data block such as 1/3 of the block, the proposed two-phase MLSE can approach the performance of the optimal exhaustive checking. In a normal case, where the training sequence consumes only 0.14 of the bandwidth, our proposed method still outperforms evidently the conventional MLSE.
About Strongly Universal Cellular Automata
Venue: arXiv cs.DM 2013
Year: 2013

In this paper, we construct a strongly universal cellular automaton on the line with 11 states and the standard neighbourhood. We embed this construction into several tilings of the hyperbolic plane and of the hyperbolic 3D space giving rise to strongly universal cellular automata with 10 states.
Semi-Optimal Edge Detector based on Simple Standard Deviation with Adjusted Thresholding
Venue: arXiv cs.CV 2013
Year: 2013

This paper proposes a novel method which combines both median filter and simple standard deviation to accomplish an excellent edge detector for image processing. First of all, a denoising process must be applied on the grey scale image using median filter to identify pixels which are likely to be contaminated by noise. The benefit of this step is to smooth the image and get rid of the noisy pixels. After that, the simple statistical standard deviation could be computed for each 2X2 window size. If the value of the standard deviation inside the 2X2 window size is greater than a predefined threshold, then the upper left pixel in the 2?2 window represents an edge. The visual differences between the proposed edge detector and the standard known edge detectors have been shown to support the contribution in this paper.
Low-Complexity Lattice Reduction-Aided Channel Inversion Methods for Large-Dimensional Multi-User MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

Low-complexity precoding {algorithms} are proposed in this work to reduce the computational complexity and improve the performance of regularized block diagonalization (RBD) {based} precoding {schemes} for large multi-user {MIMO} (MU-MIMO) systems. The proposed algorithms are based on a channel inversion technique, QR decompositions{,} and lattice reductions to decouple the MU-MIMO channel into equivalent SU-MIMO channels. Simulation results show that the proposed precoding algorithms can achieve almost the same sum-rate performance as RBD precoding, substantial bit error rate (BER) performance gains{,} and a simplified receiver structure, while requiring a lower complexity.
Apricot - An Object-Oriented Modeling Language for Hybrid Systems
Venue: arXiv cs.SE 2013
Year: 2013

We propose Apricot as an object-oriented language for modeling hybrid systems. The language combines the features in domain specific language and object-oriented language, that fills the gap between design and implementation, as a result, we put forward the modeling language with simple and distinct syntax, structure and semantics. In addition, we introduce the concept of design by convention into Apricot.As the characteristic of object-oriented and the component architecture in Apricot, we conclude that it is competent for modeling hybrid systems without losing scalability.