OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Control of Tunable Sub-optimal Algorithms for Scheduling of Time-varying Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

It is well known that for ergodic channel processes the Generalized Max-Weight Matching (GMWM) scheduling policy stabilizes the network for any supportable arrival rate vector within the network capacity region. This policy, however, often requires the solution of an NP-hard optimization problem. This has motivated many researchers to develop sub-optimal algorithms that approximate the GMWM policy in selecting schedule vectors. One implicit assumption commonly shared in this context is that during the algorithm runtime, the channel states remain effectively unchanged. This assumption may not hold as the time needed to select near-optimal schedule vectors usually increases quickly with the network size. In this paper, we incorporate channel variations and the time-efficiency of sub-optimal algorithms into the scheduler design, to dynamically tune the algorithm runtime considering the tradeoff between algorithm efficiency and its robustness to changing channel states. Specifically, we propose a Dynamic Control Policy (DCP) that operates on top of a given sub-optimal algorithm, and dynamically but in a large time-scale adjusts the time given to the algorithm according to queue backlog and channel correlations. This policy does not require knowledge of the structure of the given sub-optimal algorithm, and with low overhead can be implemented in a distributed manner. Using a novel Lyapunov analysis, we characterize the throughput stability region induced by DCP and show that our characterization can be tight. We also show that the throughput stability region of DCP is at least as large as that of any other static policy. Finally, we provide two case studies to gain further intuition into the performance of DCP.
Constellation Precoded Beamforming
Venue: arXiv cs.IT 2009
Year: 2009

We present and analyze the performance of constellation precoded beamforming. This multi-input multi-output transmission technique is based on the singular value decomposition of a channel matrix. In this work, the beamformer is precoded to improve its diversity performance. It was shown previously that while single beamforming achieves full diversity without channel coding, multiple beamforming results in diversity loss. In this paper, we show that a properly designed constellation precoder makes uncoded multiple beamforming achieve full diversity order. We also show that partially precoded multiple beamforming gets better diversity order than multiple beamforming without constellation precoder if the subchannels to be precoded are properly chosen. We propose several criteria to design the constellation precoder. Simulation results match the analysis, and show that precoded multiple beamforming actually outperforms single beamforming without precoding at the same system data rate while achieving full diversity order.
Extensible Component Based Architecture for FLASH, A Massively Parallel, Multiphysics Simulation Code
Venue: arXiv cs.SE 2009
Year: 2009

FLASH is a publicly available high performance application code which has evolved into a modular, extensible software system from a collection of unconnected legacy codes. FLASH has been successful because its capabilities have been driven by the needs of scientific applications, without compromising maintainability, performance, and usability. In its newest incarnation, FLASH3 consists of inter-operable modules that can be combined to generate different applications. The FLASH architecture allows arbitrarily many alternative implementations of its components to co-exist and interchange with each other, resulting in greater flexibility. Further, a simple and elegant mechanism exists for customization of code functionality without the need to modify the core implementation of the source. A built-in unit test framework providing verifiability, combined with a rigorous software maintenance process, allow the code to operate simultaneously in the dual mode of production and development. In this paper we describe the FLASH3 architecture, with emphasis on solutions to the more challenging conflicts arising from solver complexity, portable performance requirements, and legacy codes. We also include results from user surveys conducted in 2005 and 2007, which highlight the success of the code.
Time manipulation technique for speeding up reinforcement learning in simulations
Venue: arXiv cs.AI 2009
Year: 2009

A technique for speeding up reinforcement learning algorithms by using time manipulation is proposed. It is applicable to failure-avoidance control problems running in a computer simulation. Turning the time of the simulation backwards on failure events is shown to speed up the learning by 260% and improve the state space exploration by 12% on the cart-pole balancing task, compared to the conventional Q-learning and Actor-Critic algorithms.
Analysis Paralysis: when to stop?
Venue: arXiv cs.SE 2009
Year: 2009

Analysis of a system constitutes the most important aspect of the systems development life cycle.But it is also the most confusing and time consuming of all the stages.The critical question always remains: How much and till when to analyse? Ed Yourdon has called this phenomenon as Analysis Paralysis. In this paper, I suggest a model which can actually help in arriving at a satisfactory answer to this problem.
Digital Restoration of Ancient Papyri
Venue: arXiv cs.CV 2009
Year: 2009

Image processing can be used for digital restoration of ancient papyri, that is, for a restoration performed on their digital images. The digital manipulation allows reducing the background signals and enhancing the readability of texts. In the case of very old and damaged documents, this is fundamental for identification of the patterns of letters. Some examples of restoration, obtained with an image processing which uses edges detection and Fourier filtering, are shown. One of them concerns 7Q5 fragment of the Dead Sea Scrolls.
Comparing Bibliometric Statistics Obtained from the Web of Science and Scopus
Venue: arXiv cs.IR 2009
Year: 2009

For more than 40 years, the Institute for Scientific Information (ISI, now part of Thomson Reuters) produced the only available bibliographic databases from which bibliometricians could compile large-scale bibliometric indicators. ISI's citation indexes, now regrouped under the Web of Science (WoS), were the major sources of bibliometric data until 2004, when Scopus was launched by the publisher Reed Elsevier. For those who perform bibliometric analyses and comparisons of countries or institutions, the existence of these two major databases raises the important question of the comparability and stability of statistics obtained from different data sources. This paper uses macro-level bibliometric indicators to compare results obtained from the WoS and Scopus. It shows that the correlations between the measures obtained with both databases for the number of papers and the number of citations received by countries, as well as for their ranks, are extremely high (R2 > .99). There is also a very high correlation when countries' papers are broken down by field. The paper thus provides evidence that indicators of scientific production and citations at the country level are stable and largely independent of the database.
Heterogeneous knowledge representation using a finite automaton and first order logic: a case study in electromyography
Venue: arXiv cs.AI 2009
Year: 2009

In a certain number of situations, human cognitive functioning is difficult to represent with classical artificial intelligence structures. Such a difficulty arises in the polyneuropathy diagnosis which is based on the spatial distribution, along the nerve fibres, of lesions, together with the synthesis of several partial diagnoses. Faced with this problem while building up an expert system (NEUROP), we developed a heterogeneous knowledge representation associating a finite automaton with first order logic. A number of knowledge representation problems raised by the electromyography test features are examined in this study and the expert system architecture allowing such a knowledge modeling are laid out.
A Stochastic View of Optimal Regret through Minimax Duality
Venue: arXiv cs.LG 2009
Year: 2009

We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary.
Testing Goodness-of-Fit via Rate Distortion
Venue: arXiv cs.IT 2009
Year: 2009

A framework is developed using techniques from rate distortion theory in statistical testing. The idea is first to do optimal compression according to a certain distortion function and then use information divergence from the compressed empirical distribution to the compressed null hypothesis as statistic. Only very special cases have been studied in more detail, but they indicate that the approach can be used under very general conditions.
On Solving Boolean Multilevel Optimization Problems
Venue: arXiv cs.LO 2009
Year: 2009

Many combinatorial optimization problems entail a number of hierarchically dependent optimization problems. An often used solution is to associate a suitably large cost with each individual optimization problem, such that the solution of the resulting aggregated optimization problem solves the original set of hierarchically dependent optimization problems. This paper starts by studying the package upgradeability problem in software distributions. Straightforward solutions based on Maximum Satisfiability (MaxSAT) and pseudo-Boolean (PB) optimization are shown to be ineffective, and unlikely to scale for large problem instances. Afterwards, the package upgradeability problem is related to multilevel optimization. The paper then develops new algorithms for Boolean Multilevel Optimization (BMO) and highlights a large number of potential applications. The experimental results indicate that the proposed algorithms for BMO allow solving optimization problems that existing MaxSAT and PB solvers would otherwise be unable to solve.
Stiffness Analysis of Overconstrained Parallel Manipulators
Venue: arXiv cs.RO 2009
Year: 2009

The paper presents a new stiffness modeling method for overconstrained parallel manipulators with flexible links and compliant actuating joints. It is based on a multidimensional lumped-parameter model that replaces the link flexibility by localized 6-dof virtual springs that describe both translational/rotational compliance and the coupling between them. In contrast to other works, the method involves a FEA-based link stiffness evaluation and employs a new solution strategy of the kinetostatic equations for the unloaded manipulator configuration, which allows computing the stiffness matrix for the overconstrained architectures, including singular manipulator postures. The advantages of the developed technique are confirmed by application examples, which deal with comparative stiffness analysis of two translational parallel manipulators of 3-PUU and 3-PRPaR architectures. Accuracy of the proposed approach was evaluated for a case study, which focuses on stiffness analysis of Orthoglide parallel manipulator.
Holographic algorithms without matchgates
Venue: arXiv cs.CC 2009
Year: 2009

The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, yields insight into the hierarchy of complexity classes. In particular, the theory produces algebraic tests for a problem to be in the class P. In this article we streamline the implementation of holographic algorithms by eliminating one of the steps in the construction procedure, and generalize their applicability to new signatures. Instead of matchgates, which are weighted graph fragments that replace vertices of a natural bipartite graph G associated to a problem P, our approach uses only only a natural number-of-edges by number-of-edges matrix associated to G. An easy-to-compute multiple of its Pfaffian is the number of solutions to the counting problem. This simplification improves our understanding of the applicability of holographic algorithms, indicates a more geometric approach to complexity classes, and facilitates practical implementations. The generalized applicability arises because our approach allows for new algebraic tests that are different from the "Grassmann-Plucker identities" used up until now. Natural problems treatable by these new methods have been previously considered in a different context, and we present one such example.
The Minimal Polynomial over F_q of Linear Recurring Sequence over F_{q^m}
Venue: arXiv cs.IT 2009
Year: 2009

Recently, motivated by the study of vectorized stream cipher systems, the joint linear complexity and joint minimal polynomial of multisequences have been investigated. Let S be a linear recurring sequence over finite field F_{q^m} with minimal polynomial h(x) over F_{q^m}. Since F_{q^m} and F_{q}^m are isomorphic vector spaces over the finite field F_q, S is identified with an m-fold multisequence S^{(m)} over the finite field F_q. The joint minimal polynomial and joint linear complexity of the m-fold multisequence S^{(m)} are the minimal polynomial and linear complexity over F_q of S respectively. In this paper, we study the minimal polynomial and linear complexity over F_q of a linear recurring sequence S over F_{q^m} with minimal polynomial h(x) over F_{q^m}. If the canonical factorization of h(x) in F_{q^m}[x] is known, we determine the minimal polynomial and linear complexity over F_q of the linear recurring sequence S over F_{q^m}.
Mission-Aware Medium Access Control in Random Access Networks
Venue: arXiv cs.NI 2009
Year: 2009

We study mission-critical networking in wireless communication networks, where network users are subject to critical events such as emergencies and crises. If a critical event occurs to a user, the user needs to send necessary information for help as early as possible. However, most existing medium access control (MAC) protocols are not adequate to meet the urgent need for information transmission by users in a critical situation. In this paer, we propose a novel class of MAC protocols that utilize available past information as well as current information. Our proposed protocols are mission-aware since they prescribe different transmission decision rules to users in different situations. We show that the proposed protocols perform well not only when the system faces a critical situation but also when there is no critical situation. By utilizing past information, the proposed protocols coordinate transmissions by users to achieve high throughput in the normal phase of operation and to let a user in a critical situation make successful transmissions while it is in the critical situation. Moreover, the proposed protocols require short memory and no message exchanges.
Moveable objects and applications, based on them
Venue: arXiv cs.HC 2009
Year: 2009

The inner views of all our applications are predetermined by the designers; only some non-significant variations are allowed with the help of adaptive interface. In several programs you can find some moveable objects, but it is an extremely rare thing. However, the design of applications on the basis of moveable and resizable objects opens an absolutely new way of programming; such applications are much more effective in users' work, because each user can adjust an application to his purposes. Programs, using adaptive interface, only implement the designer's ideas of what would be the best reaction to any of the users' doings or commands. Applications on moveable elements do not have such predetermined system of rules; they are fully controlled by the users. This article describes and demonstrates the new way of applications' design.
Optimal Tableau Decision Procedures for PDL
Venue: arXiv cs.LO 2009
Year: 2009

We reformulate Pratt's tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and more direct for implementation. Extending the method we give the first EXPTIME (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove the new result that the data complexity of the instance checking problem in PDL is coNP-complete.
Codes on Planar Graphs
Venue: arXiv cs.IT 2009
Year: 2009

Codes defined on graphs and their properties have been subjects of intense recent research. On the practical side, constructions for capacity-approaching codes are graphical. On the theoretical side, codes on graphs provide several intriguing problems in the intersection of coding theory and graph theory. In this paper, we study codes defined by planar Tanner graphs. We derive an upper bound on minimum distance $d$ of such codes as a function of the code rate $R$ for $R \ge 5/8$. The bound is given by $$d\le \lceil \frac{7-8R}{2(2R-1)} \rceil + 3\le 7.$$ Among the interesting conclusions of this result are the following: (1) planar graphs do not support asymptotically good codes, and (2) finite-length, high-rate codes on graphs with high minimum distance will necessarily be non-planar.
Imaging of moving targets with multi-static SAR using an overcomplete dictionary
Venue: arXiv cs.IT 2009
Year: 2009

This paper presents a method for imaging of moving targets using multi-static SAR by treating the problem as one of spatial reflectivity signal inversion over an overcomplete dictionary of target velocities. Since SAR sensor returns can be related to the spatial frequency domain projections of the scattering field, we exploit insights from compressed sensing theory to show that moving targets can be effectively imaged with transmitters and receivers randomly dispersed in a multi-static geometry within a narrow forward cone around the scene of interest. Existing approaches to dealing with moving targets in SAR solve a coupled non-linear problem of target scattering and motion estimation typically through matched filtering. In contrast, by using an overcomplete dictionary approach we effectively linearize the forward model and solve the moving target problem as a larger, unified regularized inversion problem subject to sparsity constraints.
Maximizing the number of accepted flows in TDMA-based wireless ad hoc networks is APX-complete
Venue: arXiv cs.NI 2009
Year: 2009

Full exploitation of the bandwidth resources of Wireless Networks is challenging because of the sharing of the radio medium among neighboring nodes. Practical algorithms and distributed schemes that tries to optimising the use of the network radio resources. In this technical report we present the proof that maximising the network capacity is is an APX Complete problem (not approximable within 1/(1 - 2^(-k)) - eps for eps > 0).
An Investigation Report on Auction Mechanism Design
Venue: arXiv cs.AI 2009
Year: 2009

Auctions are markets with strict regulations governing the information available to traders in the market and the possible actions they can take. Since well designed auctions achieve desirable economic outcomes, they have been widely used in solving real-world optimization problems, and in structuring stock or futures exchanges. Auctions also provide a very valuable testing-ground for economic theory, and they play an important role in computer-based control systems. Auction mechanism design aims to manipulate the rules of an auction in order to achieve specific goals. Economists traditionally use mathematical methods, mainly game theory, to analyze auctions and design new auction forms. However, due to the high complexity of auctions, the mathematical models are typically simplified to obtain results, and this makes it difficult to apply results derived from such models to market environments in the real world. As a result, researchers are turning to empirical approaches. This report aims to survey the theoretical and empirical approaches to designing auction mechanisms and trading strategies with more weights on empirical ones, and build the foundation for further research in the field.
Cooperative Transmission for Wireless Relay Networks Using Limited Feedback
Venue: arXiv cs.IT 2009
Year: 2009

To achieve the available performance gains in half-duplex wireless relay networks, several cooperative schemes have been earlier proposed using either distributed space-time coding or distributed beamforming for the transmitter without and with channel state information (CSI), respectively. However, these schemes typically have rather high implementation and/or decoding complexities, especially when the number of relays is high. In this paper, we propose a simple low-rate feedback-based approach to achieve maximum diversity with a low decoding and implementation complexity. To further improve the performance of the proposed scheme, the knowledge of the second-order channel statistics is exploited to design long-term power loading through maximizing the receiver signal-to-noise ratio (SNR) with appropriate constraints. This maximization problem is approximated by a convex feasibility problem whose solution is shown to be close to the optimal one in terms of the error probability. Subsequently, to provide robustness against feedback errors and further decrease the feedback rate, an extended version of the distributed Alamouti code is proposed. It is also shown that our scheme can be generalized to the differential transmission case, where it can be applied to wireless relay networks with no CSI available at the receiver.
MIMO Downlink Scheduling with Non-Perfect Channel State Knowledge
Venue: arXiv cs.IT 2009
Year: 2009

Downlink scheduling schemes are well-known and widely investigated under the assumption that the channel state is perfectly known to the scheduler. In the multiuser MIMO (broadcast) case, downlink scheduling in the presence of non-perfect channel state information (CSI) is only scantly treated. In this paper we provide a general framework that addresses the problem systematically. Also, we illuminate the key role played by the channel state prediction error: our scheme treats in a fundamentally different way users with small channel prediction error ("predictable" users) and users with large channel prediction error ("non-predictable" users), and can be interpreted as a near-optimal opportunistic time-sharing strategy between MIMO downlink beamforming to predictable users and space-time coding to nonpredictable users. Our results, based on a realistic MIMO channel model used in 3GPP standardization, show that the proposed algorithms can significantly outperform a conventional "mismatched" scheduling scheme that treats the available CSI as if it was perfect.
Spatial and Temporal Correlation of the Interference in ALOHA Ad Hoc Networks
Venue: arXiv cs.IT 2009
Year: 2009

Interference is a main limiting factor of the performance of a wireless ad hoc network. The temporal and the spatial correlation of the interference makes the outages correlated temporally (important for retransmissions) and spatially correlated (important for routing). In this letter we quantify the temporal and spatial correlation of the interference in a wireless ad hoc network whose nodes are distributed as a Poisson point process on the plane when ALOHA is used as the multiple-access scheme.