OpenRaiser/Intern-Atlas huggingface dataset:
Investment and Pricing with Spectrum Uncertainty: A Cognitive Operator's Perspective
Venue: arXiv cs.NI 2010
Year: 2010

This paper studies the optimal investment and pricing decisions of a cognitive mobile virtual network operator (C-MVNO) under spectrum supply uncertainty. Compared with a traditional MVNO who often leases spectrum via long-term contracts, a C-MVNO can acquire spectrum dynamically in short-term by both sensing the empty "spectrum holes" of licensed bands and dynamically leasing from the spectrum owner. As a result, a C-MVNO can make flexible investment and pricing decisions to match the current demands of the secondary unlicensed users. Compared to dynamic spectrum leasing, spectrum sensing is typically cheaper, but the obtained useful spectrum amount is random due to primary licensed users' stochastic traffic. The C-MVNO needs to determine the optimal amounts of spectrum sensing and leasing by evaluating the trade off between cost and uncertainty. The C-MVNO also needs to determine the optimal price to sell the spectrum to the secondary unlicensed users, taking into account wireless heterogeneity of users such as different maximum transmission power levels and channel gains. We model and analyze the interactions between the C-MVNO and secondary unlicensed users as a Stackelberg game. We show several interesting properties of the network equilibrium, including threshold structures of the optimal investment and pricing decisions, the independence of the optimal price on users' wireless characteristics, and guaranteed fair and predictable QoS among users. We prove that these properties hold for general SNR regime and general continuous distributions of sensing uncertainty. We show that spectrum sensing can significantly improve the C-MVNO's expected profit and users' payoffs.
Frugal Mechanism Design via Spectral Techniques
Venue: arXiv cs.GT 2010
Year: 2010

We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [Archer&Tardos'02] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the \sqrt-mechanism for buying a path in a graph [Karlin et. al'05] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, while our mechanism is within a factor of k + 1 from optimal, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [Elkind et al.'07]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [Karlin et al.'05] and answers several open questions proposed in that paper.
Inapproximability of maximal strip recovery
Venue: arXiv cs.CC 2010
Year: 2010

In comparative genomic, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given $d$ genomic maps as sequences of gene markers, the objective of \msr{d} is to find $d$ subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant $d \ge 2$, a polynomial-time 2d-approximation for \msr{d} was previously known. In this paper, we show that for any $d \ge 2$, \msr{d} is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating \msr{d} for all $d \ge 2$. In particular, we show that \msr{d} is NP-hard to approximate within $Ω(d/\log d)$. From the other direction, we show that the previous 2d-approximation for \msr{d} can be optimized into a polynomial-time algorithm even if $d$ is not a constant but is part of the input. We then extend our inapproximability results to several related problems including \cmsr{d}, \gapmsrδ{d}, and \gapcmsrδ{d}.
Rateless Codes for Single-Server Streaming to Diverse Users
Venue: arXiv cs.IT 2010
Year: 2010

We investigate the performance of rateless codes for single-server streaming to diverse users, assuming that diversity in users is present not only because they have different channel conditions, but also because they demand different amounts of information and have different decoding capabilities. The LT encoding scheme is employed. While some users accept output symbols of all degrees and decode using belief propagation, others only collect degree- 1 output symbols and run no decoding algorithm. We propose several performance measures, and optimize the performance of the rateless code used at the server through the design of the code degree distribution. Optimization problems are formulated for the asymptotic regime and solved as linear programming problems. Optimized performance shows great improvement in total bandwidth consumption over using the conventional ideal soliton distribution, or simply sending separately encoded streams to different types of user nodes. Simulation experiments confirm the usability of the optimization results obtained for the asymptotic regime as a guideline for finite-length code design.
The Dense k Subgraph problem
Venue: arXiv cs.DM 2010
Year: 2010

Given a graph G = (V,E) and a parameter k, we consider the problem of finding a subset U in V of size k that maximizes the number of induced edges (DkS). We improve upon the previously best known approximation ratio for DkS, a ratio that has not seen any progress during the last decade. Specifically, we improve the approximation ratio from n^{0.32258} to n^{0.3159}. The improved ratio is obtained by studying a variant to the DkS problem in which one considers the problem of finding a subset U in V of size at most k that maximizes the number of induced edges. Finally, we study the DkS variant in which one considers the problem of finding a subset U in V of size at least k that maximizes the number of induced edges.
On Iterated Dominance, Matrix Elimination, and Matched Paths
Venue: arXiv cs.GT 2010
Year: 2010

We study computational problems arising from the iterated removal of weakly dominated actions in anonymous games. Our main result shows that it is NP-complete to decide whether an anonymous game with three actions can be solved via iterated weak dominance. The two-action case can be reformulated as a natural elimination problem on a matrix, the complexity of which turns out to be surprisingly difficult to characterize and ultimately remains open. We however establish connections to a matching problem along paths in a directed graph, which is computationally hard in general but can also be used to identify tractable cases of matrix elimination. We finally identify different classes of anonymous games where iterated dominance is in P and NP-complete, respectively.
Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank
Venue: arXiv cs.GT 2010
Year: 2010

Innovative auction methods can be exploited to increase profits, with Shubik's famous "dollar auction" perhaps being the most widely known example. Recently, some mainstream e-commerce web sites have apparently achieved the same end on a much broader scale, by using "pay-per-bid" auctions to sell items, from video games to bars of gold. In these auctions, bidders incur a cost for placing each bid in addition to (or sometimes in lieu of) the winner's final purchase cost. Thus even when a winner's purchase cost is a small fraction of the item's intrinsic value, the auctioneer can still profit handsomely from the bid fees. Our work provides novel analyses for these auctions, based on both modeling and datasets derived from auctions at Swoopo.com, the leading pay-per-bid auction site. While previous modeling work predicts profit-free equilibria, we analyze the impact of information asymmetry broadly, as well as Swoopo features such as bidpacks and the Swoop It Now option specifically, to quantify the effects of imperfect information in these auctions. We find that even small asymmetries across players (cheaper bids, better estimates of other players' intent, different valuations of items, committed players willing to play "chicken") can increase the auction duration well beyond that predicted by previous work and thus skew the auctioneer's profit disproportionately. Finally, we discuss our findings in the context of a dataset of thousands of live auctions we observed on Swoopo, which enables us also to examine behavioral factors, such as the power of aggressive bidding. Ultimately, our findings show that even with fully rational players, if players overlook or are unaware any of these factors, the result is outsized profits for pay-per-bid auctioneers.
Contextual Mobile Learning Strongly Related to Industrial Activities: Principles and Case Study
Venue: arXiv cs.HC 2010
Year: 2010

M-learning (mobile learning) can take various forms. We are interested in contextualized M-learning, i.e. the training related to the situation physically or logically localized. Contextualization and pervasivity are important aspects of our approach. We propose in particular MOCOCO principles (Mobility - COntextualisation - COoperation) using IMERA platform (Mobile Interaction in the Augmented Real Environment). We are studying various mobile learning contexts related to professional activities, in order to master appliances (Installation, Use, Breakdown diagnostic and Repairing). Contextualization, traceability and checking of execution of prescribed operations are based mainly on the use of RFID labels. Investigation of the appropriate training methods for this kind of learning situation, applying mainly a constructivist approach known as "Just-in-time learning", "learning by doing", "learning and doing", constitutes an important topic of this project. From an organizational point of view we are in perfect symbiosis with EPSS - Electronic Performance Support System [12] and our objective is to integrate learning in professional activities in three ways: 1/ before work i.e. to learn about coming actions, 2/ after work i.e. to learn about past actions to understand what happened and accumulate experience, 3/ during work i.e. to master the problem just-in-time
Vandalism Detection in Wikipedia: a Bag-of-Words Classifier Approach
Venue: arXiv cs.LG 2010
Year: 2010

A bag-of-words based probabilistic classifier is trained using regularized logistic regression to detect vandalism in the English Wikipedia. Isotonic regression is used to calibrate the class membership probabilities. Learning curve, reliability, ROC, and cost analysis are performed.
On the Vacationing CEO Problem: Achievable Rates and Outer Bounds
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies a class of source coding problems that combines elements of the CEO problem with the multiple description problem. In this setting, noisy versions of one remote source are observed by two nodes with encoders (which is similar to the CEO problem). However, it differs from the CEO problem in that each node must generate multiple descriptions of the source. This problem is of interest in multiple scenarios in efficient communication over networks. In this paper, an achievable region and an outer bound are presented for this problem, which is shown to be sum rate optimal for a class of distortion constraints.
Abstract Answer Set Solvers with Learning
Venue: arXiv cs.AI 2010
Year: 2010

Nieuwenhuis, Oliveras, and Tinelli (2006) showed how to describe enhancements of the Davis-Putnam-Logemann-Loveland algorithm using transition systems, instead of pseudocode. We design a similar framework for several algorithms that generate answer sets for logic programs: Smodels, Smodels-cc, Asp-Sat with Learning (Cmodels), and a newly designed and implemented algorithm Sup. This approach to describing answer set solvers makes it easier to prove their correctness, to compare them, and to design new systems.
Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, {\sc $k$-Leaf Out-Branching}, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{O(\sqrt{k} \log k)} n+ n^{O(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{O(\sqrt{k})}n + n^{O(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely {\sc $k$-Internal Out-Branching}, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{O(\sqrt{k} \log k)} + n^{O(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $ε>0$, the {\sc $k$-Directed Path} problem is solvable in time $O((1+ε)^k n^{f(ε)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.
K-tree: Large Scale Document Clustering
Venue: arXiv cs.IR 2010
Year: 2010

We introduce K-tree in an information retrieval context. It is an efficient approximation of the k-means clustering algorithm. Unlike k-means it forms a hierarchy of clusters. It has been extended to address issues with sparse representations. We compare performance and quality to CLUTO using document collections. The K-tree has a low time complexity that is suitable for large document collections. This tree structure allows for efficient disk based implementations where space requirements exceed that of main memory.
Computing a Frobenius Coin Problem decision problem in O(n^2)
Venue: arXiv cs.DS 2010
Year: 2010

Expanding on recent results of another an algorithm is presented that provides solution to the Frobenius Coin Problem in worst case O(n^2) in the magnitude of the largest denomination.
Distributed Rate Allocation Policies for Multi-Homed Video Streaming over Heterogeneous Access Networks
Venue: arXiv cs.MM 2010
Year: 2010

We consider the problem of rate allocation among multiple simultaneous video streams sharing multiple heterogeneous access networks. We develop and evaluate an analytical framework for optimal rate allocation based on observed available bit rate (ABR) and round-trip time (RTT) over each access network and video distortion-rate (DR) characteristics. The rate allocation is formulated as a convex optimization problem that minimizes the total expected distortion of all video streams. We present a distributed approximation of its solution and compare its performance against H-infinity optimal control and two heuristic schemes based on TCP-style additive-increase-multiplicative decrease (AIMD) principles. The various rate allocation schemes are evaluated in simulations of multiple high-definition (HD) video streams sharing multiple access networks. Our results demonstrate that, in comparison with heuristic AIMD-based schemes, both media-aware allocation and H-infinity optimal control benefit from proactive congestion avoidance and reduce the average packet loss rate from 45% to below 2%. Improvement in average received video quality ranges between 1.5 to 10.7 dB in PSNR for various background traffic loads and video playout deadlines. Media-aware allocation further exploits its knowledge of the video DR characteristics to achieve a more balanced video quality among all streams.
Principal manifolds and graphs in practice: from molecular biology to dynamical systems
Venue: arXiv cs.NE 2010
Year: 2010

We present several applications of non-linear data modeling, using principal manifolds and principal graphs constructed using the metaphor of elasticity (elastic principal graph approach). These approaches are generalizations of the Kohonen's self-organizing maps, a class of artificial neural networks. On several examples we show advantages of using non-linear objects for data approximation in comparison to the linear ones. We propose four numerical criteria for comparing linear and non-linear mappings of datasets into the spaces of lower dimension. The examples are taken from comparative political science, from analysis of high-throughput data in molecular biology, from analysis of dynamical systems.
Some Architectures for Chebyshev Interpolation
Venue: arXiv cs.NA 2010
Year: 2010

Digital architectures for Chebyshev interpolation are explored and a variation which is word-serial in nature is proposed. These architectures are contrasted with equispaced system structures. Further, Chebyshev interpolation scheme is compared to the conventional equispaced interpolation vis-a-vis reconstruction error and relative number of samples. It is also shown that the use of a hybrid (or dual) Analog to Digital converter unit can reduce system power consumption by as much as 1/3rd of the original.
Integer Reset Timed Automata: Clock Reduction and Determinizability
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we propose a procedure that given an integer reset timed automaton (IRTA) ${\cal A}$, produces a language equivalent deterministic one clock IRTA ${\cal B}$ whose size is at most doubly exponential in the size of ${\cal A}$. We prove that this bound on the number of locations is tight. Further, if integer resets are used in stopwatch automata, a subclass of stopwatch automata which is closed under all boolean operations and for which reachability is decidable is obtained.
Boosting k-NN for categorization of natural scenes
Venue: arXiv cs.CV 2010
Year: 2010

The k-nearest neighbors (k-NN) classification rule has proven extremely successful in countless many computer vision applications. For example, image categorization often relies on uniform voting among the nearest prototypes in the space of descriptors. In spite of its good properties, the classic k-NN rule suffers from high variance when dealing with sparse prototype datasets in high dimensions. A few techniques have been proposed to improve k-NN classification, which rely on either deforming the nearest neighborhood relationship or modifying the input space. In this paper, we propose a novel boosting algorithm, called UNN (Universal Nearest Neighbors), which induces leveraged k-NN, thus generalizing the classic k-NN rule. We redefine the voting rule as a strong classifier that linearly combines predictions from the k closest prototypes. Weak classifiers are learned by UNN so as to minimize a surrogate risk. A major feature of UNN is the ability to learn which prototypes are the most relevant for a given class, thus allowing one for effective data reduction. Experimental results on the synthetic two-class dataset of Ripley show that such a filtering strategy is able to reject "noisy" prototypes. We carried out image categorization experiments on a database containing eight classes of natural scenes. We show that our method outperforms significantly the classic k-NN classification, while enabling significant reduction of the computational cost by means of data filtering.
On Critical Relative Distance of DNA Codes for Additive Stem Similarity
Venue: arXiv cs.IT 2010
Year: 2010

We consider DNA codes based on the nearest-neighbor (stem) similarity model which adequately reflects the "hybridization potential" of two DNA sequences. Our aim is to present a survey of bounds on the rate of DNA codes with respect to a thermodynamically motivated similarity measure called an additive stem similarity. These results yield a method to analyze and compare known samples of the nearest neighbor "thermodynamic weights" associated to stacked pairs that occurred in DNA secondary structures.
Quality Control and Validation Boundaries in a Triple Helix of University-Industry-Government: 'Mode 2' and the Future of University Research
Venue: arXiv cs.CY 2010
Year: 2010

How is quality control organized in the new "Mode 2" of the production of scientific knowledge? When institutional boundaries are increasingly blurred in a Triple Helix of University-Industry-Government relations, criteria for quality control in the production of scientific knowledge can be expected to change at the interfaces. The categorization in terms of two modes of knowledge production was introduced by Gibbons et al. (1994) in order to describe changes in the networks of scientific communications (funding patterns, research configurations, styles of knowledge management, etc.). These changes were mainly specified as institutional parameters in order to deal with the subjects of R&D management and S&T policies, that is, ex ante (Spiegel-Ring 1973 Van den Daele et al. 1979). We focus on the 'validation boundaries' emerging from the differences between Mode 1 and Mode 2 that is, on the criteria for quality control that can analytically and reflexively be brought to the fore ex post. The shift from an institutional frame of reference to a focus on the dynamics of communications enables us to clarify several problems in the discussion of the future of university research.