OpenRaiser/Intern-Atlas huggingface dataset:
A Spectrum-Shaping Perspective on Cognitive Radio
Venue: arXiv cs.IT 2008
Year: 2008

A new perspective on cognitive radio is presented, where the pre-existent legacy service is either uncoded or coded and a pair of cognitive transceivers need be appropriately deployed to coexist with the legacy service. The basic idea underlying the new perspective is to exploit the fact that, typically, the legacy channel is not fully loaded by the legacy service, thus leaving a non-negligible margin to accommodate the cognitive transmission. The exploitation of such a load margin is optimized by shaping the spectrum of the transmitted cognitive signal. It is shown that non-trivial coexistence of legacy and cognitive systems is possible even without sharing the legacy message with the cognitive transmitter. Surprisingly, the optimized cognitive transmitter is no longer limited by its interference power at the legacy receiver, and can always transmit at its full available device power. Analytical development and numerical illustration are presented, in particular focusing on the logarithmic growth rate, {\it i.e.}, the prelog coefficient, of cognitive transmission in the high-power regime.
Proposition of the Interactive Pareto Iterated Local Search Procedure - Elements and Initial Experiments
Venue: arXiv cs.AI 2008
Year: 2008

The article presents an approach to interactively solve multi-objective optimization problems. While the identification of efficient solutions is supported by computational intelligence techniques on the basis of local search, the search is directed by partial preference information obtained from the decision maker. An application of the approach to biobjective portfolio optimization, modeled as the well-known knapsack problem, is reported, and experimental results are reported for benchmark instances taken from the literature. In brief, we obtain encouraging results that show the applicability of the approach to the described problem.
Bin Packing Under Multiple Objectives - a Heuristic Approximation Approach
Venue: arXiv cs.AI 2008
Year: 2008

The article proposes a heuristic approximation approach to the bin packing problem under multiple objectives. In addition to the traditional objective of minimizing the number of bins, the heterogeneousness of the elements in each bin is minimized, leading to a biobjective formulation of the problem with a tradeoff between the number of bins and their heterogeneousness. An extension of the Best-Fit approximation algorithm is presented to solve the problem. Experimental investigations have been carried out on benchmark instances of different size, ranging from 100 to 1000 items. Encouraging results have been obtained, showing the applicability of the heuristic approach to the described problem.
An application of the Threshold Accepting metaheuristic for curriculum based course timetabling
Venue: arXiv cs.AI 2008
Year: 2008

The article presents a local search approach for the solution of timetabling problems in general, with a particular implementation for competition track 3 of the International Timetabling Competition 2007 (ITC 2007). The heuristic search procedure is based on Threshold Accepting to overcome local optima. A stochastic neighborhood is proposed and implemented, randomly removing and reassigning events from the current solution. The overall concept has been incrementally obtained from a series of experiments, which we describe in each (sub)section of the paper. In result, we successfully derived a potential candidate solution approach for the finals of track 3 of the ITC 2007.
Managing Varying Worst Case Execution Times on DVS Platforms
Venue: arXiv cs.OS 2008
Year: 2008

Energy efficient real-time task scheduling attracted a lot of attention in the past decade. Most of the time, deterministic execution lengths for tasks were considered, but this model fits less and less with the reality, especially with the increasing number of multimedia applications. It's why a lot of research is starting to consider stochastic models, where execution times are only known stochastically. However, authors consider that they have a pretty much precise knowledge about the properties of the system, especially regarding to the worst case execution time (or worst case execution cycles, WCEC). In this work, we try to relax this hypothesis, and assume that the WCEC can vary. We propose miscellaneous methods to react to such a situation, and give many simulation results attesting that with a small effort, we can provide very good results, allowing to keep a low deadline miss rate as well as an energy consumption similar to clairvoyant algorithms.
Minkowski Sum Selection and Finding
Venue: arXiv cs.DS 2008
Year: 2008

For the \textsc{Minkowski Sum Selection} problem with linear objective functions, we obtain the following results: (1) optimal $O(n\log n)$ time algorithms for $λ=1$; (2) $O(n\log^2 n)$ time deterministic algorithms and expected $O(n\log n)$ time randomized algorithms for any fixed $λ>1$. For the \textsc{Minkowski Sum Finding} problem with linear objective functions or objective functions of the form $f(x,y)=\frac{by}{ax}$, we construct optimal $O(n\log n)$ time algorithms for any fixed $λ\geq 1$.
The Golden Ratio Encoder
Venue: arXiv cs.IT 2008
Year: 2008

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder where the value of the base beta is equal to golden mean. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. A formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is also proposed.
Predictive Hypothesis Identification
Venue: arXiv cs.LG 2008
Year: 2008

While statistics focusses on hypothesis testing and on estimating (properties of) the true sampling distribution, in machine learning the performance of learning algorithms on future data is the primary issue. In this paper we bridge the gap with a general principle (PHI) that identifies hypotheses with best predictive performance. This includes predictive point and interval estimation, simple and composite hypothesis testing, (mixture) model selection, and others as special cases. For concrete instantiations we will recover well-known methods, variations thereof, and new ones. PHI nicely justifies, reconciles, and blends (a reparametrization invariant variation of) MAP, ML, MDL, and moment estimation. One particular feature of PHI is that it can genuinely deal with nested hypotheses.
What makes a good role model
Venue: arXiv cs.IT 2008
Year: 2008

The role model strategy is introduced as a method for designing an estimator by approaching the output of a superior estimator that has better input observations. This strategy is shown to yield the optimal Bayesian estimator when a Markov condition is fulfilled. Two examples involving simple channels are given to illustrate its use. The strategy is combined with time averaging to construct a statistical model by numerically solving a convex program. The role model strategy was developed in the context of low complexity decoder design for iterative decoding. Potential applications outside the field of communications are discussed.
Obtaining Exact Interpolation Multivariate Polynomial by Approximation
Venue: arXiv cs.SC 2008
Year: 2008

In some fields such as Mathematics Mechanization, automated reasoning and Trustworthy Computing etc., exact results are needed. Symbolic computations are used to obtain the exact results. Symbolic computations are of high complexity. In order to improve the situation, exactly interpolating methods are often proposed for the exact results and approximate interpolating methods for the approximate ones. In this paper, we study how to obtain exact interpolation polynomial with rational coefficients by approximate interpolating methods.
An optimal local approximation algorithm for max-min linear programs
Venue: arXiv cs.DC 2008
Year: 2008

We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The objective is to maximise $ω$ subject to $Ax \le 1$, $Cx \ge ω1$, and $x \ge 0$ for nonnegative matrices $A$ and $C$. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.
Mumford dendrograms and discrete p-adic symmetries
Venue: arXiv cs.DM 2008
Year: 2008

In this article, we present an effective encoding of dendrograms by embedding them into the Bruhat-Tits trees associated to $p$-adic number fields. As an application, we show how strings over a finite alphabet can be encoded in cyclotomic extensions of $\mathbb{Q}_p$ and discuss $p$-adic DNA encoding. The application leads to fast $p$-adic agglomerative hierarchic algorithms similar to the ones recently used e.g. by A. Khrennikov and others. From the viewpoint of $p$-adic geometry, to encode a dendrogram $X$ in a $p$-adic field $K$ means to fix a set $S$ of $K$-rational punctures on the $p$-adic projective line $\mathbb{P}^1$. To $\mathbb{P}^1\setminus S$ is associated in a natural way a subtree inside the Bruhat-Tits tree which recovers $X$, a method first used by F. Kato in 1999 in the classification of discrete subgroups of $\textrm{PGL}_2(K)$. Next, we show how the $p$-adic moduli space $\mathfrak{M}_{0,n}$ of $\mathbb{P}^1$ with $n$ punctures can be applied to the study of time series of dendrograms and those symmetries arising from hyperbolic actions on $\mathbb{P}^1$. In this way, we can associate to certain classes of dynamical systems a Mumford curve, i.e. a $p$-adic algebraic curve with totally degenerate reduction modulo $p$. Finally, we indicate some of our results in the study of general discrete actions on $\mathbb{P}^1$, and their relation to $p$-adic Hurwitz spaces.
Topological Complexity of omega-Powers : Extended Abstract
Venue: arXiv cs.LO 2008
Year: 2008

This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper "Classical and effective descriptive complexities of omega-powers" available from arXiv:0708.4176) and reflecting also some open questions which were discussed during the Dagstuhl seminar on "Topological and Game-Theoretic Aspects of Infinite Computations" 29.06.08 - 04.07.08.
The complexity of counting solutions to Generalised Satisfiability Problems modulo k
Venue: arXiv cs.CC 2008
Year: 2008

Generalised Satisfiability Problems (or Boolean Constraint Satisfaction Problems), introduced by Schaefer in 1978, are a general class of problem which allow the systematic study of the complexity of satisfiability problems with different types of constraints. In 1979, Valiant introduced the complexity class parity P, the problem of counting the number of solutions to NP problems modulo two. Others have since considered the question of counting modulo other integers. We give a dichotomy theorem for the complexity of counting the number of solutions to Generalised Satisfiability Problems modulo integers. This follows from an earlier result of Creignou and Hermann which gave a counting dichotomy for these types of problem, and the dichotomy itself is almost identical. Specifically, counting the number of solutions to a Generalised Satisfiability Problem can be done in polynomial time if all the relations are affine. Otherwise, except for one special case with k = 2, it is #_kP-complete.
Distributed Detection in Sensor Networks with Limited Range Multi-Modal Sensors
Venue: arXiv cs.IT 2008
Year: 2008

We consider a multi-object detection problem over a sensor network (SNET) with limited range multi-modal sensors. Limited range sensing environment arises in a sensing field prone to signal attenuation and path losses. The general problem complements the widely considered decentralized detection problem where all sensors observe the same object. In this paper we develop a distributed detection approach based on recent development of the false discovery rate (FDR) and the associated BH test procedure. The BH procedure is based on rank ordering of scalar test statistics. We first develop scalar test statistics for multidimensional data to handle multi-modal sensor observations and establish its optimality in terms of the BH procedure. We then propose a distributed algorithm in the ideal case of infinite attenuation for identification of sensors that are in the immediate vicinity of an object. We demonstrate communication message scalability to large SNETs by showing that the upper bound on the communication message complexity scales linearly with the number of sensors that are in the vicinity of objects and is independent of the total number of sensors in the SNET. This brings forth an important principle for evaluating the performance of an SNET, namely, the need for scalability of communications and performance with respect to the number of objects or events in an SNET irrespective of the network size. We then account for finite attenuation by modeling sensor observations as corrupted by uncertain interference arising from distant objects and developing robust extensions to our idealized distributed scheme. The robustness properties ensure that both the error performance and communication message complexity degrade gracefully with interference.
Reliable Communications with Asymmetric Codebooks: An Information Theoretic Analysis of Robust Signal Hashing
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a generalization of the traditional point-to-point to communication setup, which is named as "reliable communications with asymmetric codebooks", is proposed. Under the assumption of independent identically distributed (i.i.d) encoder codewords, it is proven that the operational capacity of the system is equal to the information capacity of the system, which is given by $\max_{p(x)} I(U;Y)$, where $X, U$ and $Y$ denote the individual random elements of encoder codewords, decoder codewords and decoder inputs. The capacity result is derived in the "binary symmetric" case (which is an analogous formulation of the traditional "binary symmetric channel" for our case), as a function of the system parameters. A conceptually insightful inference is made by attributing the difference from the classical Shannon-type capacity of binary symmetric channel to the {\em gap} due to the codebook asymmetry.
Materialized View Selection by Query Clustering in XML Data Warehouses
Venue: arXiv cs.DB 2008
Year: 2008

XML data warehouses form an interesting basis for decision-support applications that exploit complex data. However, native XML database management systems currently bear limited performances and it is necessary to design strategies to optimize them. In this paper, we propose an automatic strategy for the selection of XML materialized views that exploits a data mining technique, more precisely the clustering of the query workload. To validate our strategy, we implemented an XML warehouse modeled along the XCube specifications. We executed a workload of XQuery decision-support queries on this warehouse, with and without using our strategy. Our experimental results demonstrate its efficiency, even when queries are complex.
Distributing Labels on Infinite Trees
Venue: arXiv cs.DM 2008
Year: 2008

Sturmian words are infinite binary words with many equivalent definitions: They have a minimal factor complexity among all aperiodic sequences; they are balanced sequences (the labels 0 and 1 are as evenly distributed as possible) and they can be constructed using a mechanical definition. All this properties make them good candidates for being extremal points in scheduling problems over two processors. In this paper, we consider the problem of generalizing Sturmian words to trees. The problem is to evenly distribute labels 0 and 1 over infinite trees. We show that (strongly) balanced trees exist and can also be constructed using a mechanical process as long as the tree is irrational. Such trees also have a minimal factor complexity. Therefore they bring the hope that extremal scheduling properties of Sturmian words can be extended to such trees, as least partially. Such possible extensions are illustrated by one such example.
Fairness in Combinatorial Auctioning Systems
Venue: arXiv cs.GT 2008
Year: 2008

One of the Multi-Agent Systems that is widely used by various government agencies, buyers and sellers in a market economy, in such a manner so as to attain optimized resource allocation, is the Combinatorial Auctioning System (CAS). We study another important aspect of resource allocations in CAS, namely fairness. We present two important notions of fairness in CAS, extended fairness and basic fairness. We give an algorithm that works by incorporating a metric to ensure fairness in a CAS that uses the Vickrey-Clark-Groves (VCG) mechanism, and uses an algorithm of Sandholm to achieve optimality. Mathematical formulations are given to represent measures of extended fairness and basic fairness.
The fast intersection transform with applications to counting paths
Venue: arXiv cs.DS 2008
Year: 2008

We present an algorithm for evaluating a linear ``intersection transform'' of a function defined on the lattice of subsets of an $n$-element set. In particular, the algorithm constructs an arithmetic circuit for evaluating the transform in ``down-closure time'' relative to the support of the function and the evaluation domain. As an application, we develop an algorithm that, given as input a digraph with $n$ vertices and bounded integer weights at the edges, counts paths by weight and given length $0\leq\ell\leq n-1$ in time $O^*(\exp(n\cdot H(\ell/(2n))))$, where $H(p)=-p\log p-(1-p)\log(1-p)$, and the notation $O^*(\cdot)$ suppresses a factor polynomial in $n$.
Code diversity in multiple antenna wireless communication
Venue: arXiv cs.IT 2008
Year: 2008

The standard approach to the design of individual space-time codes is based on optimizing diversity and coding gains. This geometric approach leads to remarkable examples, such as perfect space-time block codes, for which the complexity of Maximum Likelihood (ML) decoding is considerable. Code diversity is an alternative and complementary approach where a small number of feedback bits are used to select from a family of space-time codes. Different codes lead to different induced channels at the receiver, where Channel State Information (CSI) is used to instruct the transmitter how to choose the code. This method of feedback provides gains associated with beamforming while minimizing the number of feedback bits. It complements the standard approach to code design by taking advantage of different (possibly equivalent) realizations of a particular code design. Feedback can be combined with sub-optimal low complexity decoding of the component codes to match ML decoding performance of any individual code in the family. It can also be combined with ML decoding of the component codes to improve performance beyond ML decoding performance of any individual code. One method of implementing code diversity is the use of feedback to adapt the phase of a transmitted signal as shown for 4 by 4 Quasi-Orthogonal Space-Time Block Code (QOSTBC) and multi-user detection using the Alamouti code. Code diversity implemented by selecting from equivalent variants is used to improve ML decoding performance of the Golden code. This paper introduces a family of full rate circulant codes which can be linearly decoded by fourier decomposition of circulant matrices within the code diversity framework. A 3 by 3 circulant code is shown to outperform the Alamouti code at the same transmission rate.
Spectrum Sharing between Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of two wireless networks operating on the same (presumably unlicensed) frequency band. Pairs within a given network cooperate to schedule transmissions, but between networks there is competition for spectrum. To make the problem tractable, we assume transmissions are scheduled according to a random access protocol where each network chooses an access probability for its users. A game between the two networks is defined. We characterize the Nash Equilibrium behavior of the system. Three regimes are identified; one in which both networks simultaneously schedule all transmissions; one in which the denser network schedules all transmissions and the sparser only schedules a fraction; and one in which both networks schedule only a fraction of their transmissions. The regime of operation depends on the pathloss exponent $α$, the latter regime being desirable, but attainable only for $α>4$. This suggests that in certain environments, rival wireless networks may end up naturally cooperating. To substantiate our analytical results, we simulate a system where networks iteratively optimize their access probabilities in a greedy manner. We also discuss a distributed scheduling protocol that employs carrier sensing, and demonstrate via simulations, that again a near cooperative equilibrium exists for sufficiently large $α$.
On an algorithm that generates an interesting maximal set P(n) of the naturals for any n greater than or equal to 2
Venue: arXiv cs.DM 2008
Year: 2008

The paper considers the problem of finding the largest possible set P(n), a subset of the set N of the natural numbers, with the property that a number is in P(n) if and only if it is a sum of n distinct naturals all in P(n) or none in P(n). Here largest is in the set theoretic sense and n is greater than or equal to 2. We call P(n) a maximal set obeying this property. For small n say 2 or 3, it is possible to develop P(n) intuitively but we strongly felt the necessity of an algorithm for any n greater than or equal to 2. Now P(n) shall invariably be a infinite set so we define another set Q(n) such that Q(n)=N-P(n), prove that Q(n) is finite and, since P(n) is automatically known if Q(n) is known, design an algorithm of worst case O(1) complexity which generates Q(n).
Framework for Dynamic Evaluation of Muscle Fatigue in Manual Handling Work
Venue: arXiv cs.RO 2008
Year: 2008

Muscle fatigue is defined as the point at which the muscle is no longer able to sustain the required force or work output level. The overexertion of muscle force and muscle fatigue can induce acute pain and chronic pain in human body. When muscle fatigue is accumulated, the functional disability can be resulted as musculoskeletal disorders (MSD). There are several posture exposure analysis methods useful for rating the MSD risks, but they are mainly based on static postures. Even in some fatigue evaluation methods, muscle fatigue evaluation is only available for static postures, but not suitable for dynamic working process. Meanwhile, some existing muscle fatigue models based on physiological models cannot be easily used in industrial ergonomic evaluations. The external dynamic load is definitely the most important factor resulting muscle fatigue, thus we propose a new fatigue model under a framework for evaluating fatigue in dynamic working processes. Under this framework, virtual reality system is taken to generate virtual working environment, which can be interacted with the work with haptic interfaces and optical motion capture system. The motion information and load information are collected and further processed to evaluate the overall work load of the worker based on dynamic muscle fatigue models and other work evaluation criterions and to give new information to characterize the penibility of the task in design process.