OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions
Venue: arXiv cs.GT 2010
Year: 2010

We design algorithms for computing approximately revenue-maximizing {\em sequential posted-pricing mechanisms (SPM)} in $K$-unit auctions, in a standard Bayesian model. A seller has $K$ copies of an item to sell, and there are $n$ buyers, each interested in only one copy, who have some value for the item. The seller must post a price for each buyer, the buyers arrive in a sequence enforced by the seller, and a buyer buys the item if its value exceeds the price posted to it. The seller does not know the values of the buyers, but have Bayesian information about them. An SPM specifies the ordering of buyers and the posted prices, and may be {\em adaptive} or {\em non-adaptive} in its behavior. The goal is to design SPM in polynomial time to maximize expected revenue. We compare against the expected revenue of optimal SPM, and provide a polynomial time approximation scheme (PTAS) for both non-adaptive and adaptive SPMs. This is achieved by two algorithms: an efficient algorithm that gives a $(1-\frac{1}{\sqrt{2πK}})$-approximation (and hence a PTAS for sufficiently large $K$), and another that is a PTAS for constant $K$. The first algorithm yields a non-adaptive SPM that yields its approximation guarantees against an optimal adaptive SPM -- this implies that the {\em adaptivity gap} in SPMs vanishes as $K$ becomes larger.
A Learning Algorithm based on High School Teaching Wisdom
Venue: arXiv cs.AI 2010
Year: 2010

A learning algorithm based on primary school teaching and learning is presented. The methodology is to continuously evaluate a student and to give them training on the examples for which they repeatedly fail, until, they can correctly answer all types of questions. This incremental learning procedure produces better learning curves by demanding the student to optimally dedicate their learning time on the failed examples. When used in machine learning, the algorithm is found to train a machine on a data with maximum variance in the feature space so that the generalization ability of the network improves. The algorithm has interesting applications in data mining, model evaluations and rare objects discovery.
State Complexity of Catenation Combined with Star and Reversal
Venue: arXiv cs.FL 2010
Year: 2010

This paper is a continuation of our research work on state complexity of combined operations. Motivated by applications, we study the state complexities of two particular combined operations: catenation combined with star and catenation combined with reversal. We show that the state complexities of both of these combined operations are considerably less than the compositions of the state complexities of their individual participating operations.
State Elimination Ordering Strategies: Some Experimental Results
Venue: arXiv cs.FL 2010
Year: 2010

Recently, the problem of obtaining a short regular expression equivalent to a given finite automaton has been intensively investigated. Algorithms for converting finite automata to regular expressions have an exponential blow-up in the worst-case. To overcome this, simple heuristic methods have been proposed. In this paper we analyse some of the heuristics presented in the literature and propose new ones. We also present some experimental comparative results based on uniform random generated deterministic finite automata.
Learning Residual Finite-State Automata Using Observation Tables
Venue: arXiv cs.FL 2010
Year: 2010

We define a two-step learner for RFSAs based on an observation table by using an algorithm for minimal DFAs to build a table for the reversal of the language in question and showing that we can derive the minimal RFSA from it after some simple modifications. We compare the algorithm to two other table-based ones of which one (by Bollig et al. 2009) infers a RFSA directly, and the other is another two-step learner proposed by the author. We focus on the criterion of query complexity.
Space and the Synchronic A-Ram
Venue: arXiv cs.CL 2010
Year: 2010

Space is a circuit oriented, spatial programming language designed to exploit the massive parallelism available in a novel formal model of computation called the Synchronic A-Ram, and physically related FPGA and reconfigurable architectures. Space expresses variable grained MIMD parallelism, is modular, strictly typed, and deterministic. Barring operations associated with memory allocation and compilation, modules cannot access global variables, and are referentially transparent. At a high level of abstraction, modules exhibit a small, sequential state transition system, aiding verification. Space deals with communication, scheduling, and resource contention issues in parallel computing, by resolving them explicitly in an incremental manner, module by module, whilst ascending the ladder of abstraction. Whilst the Synchronic A-Ram model was inspired by linguistic considerations, it is also put forward as a formal model for reconfigurable digital circuits. A programming environment has been developed, that incorporates a simulator and compiler that transform Space programs into Synchronic A-Ram machine code, consisting of only three bit-level instructions, and a marking instruction. Space and the Synchronic A-Ram point to novel routes out of the parallel computing crisis.
Biometric Authentication using Nonparametric Methods
Venue: arXiv cs.CV 2010
Year: 2010

The physiological and behavioral trait is employed to develop biometric authentication systems. The proposed work deals with the authentication of iris and signature based on minimum variance criteria. The iris patterns are preprocessed based on area of the connected components. The segmented image used for authentication consists of the region with large variations in the gray level values. The image region is split into quadtree components. The components with minimum variance are determined from the training samples. Hu moments are applied on the components. The summation of moment values corresponding to minimum variance components are provided as input vector to k-means and fuzzy k-means classifiers. The best performance was obtained for MMU database consisting of 45 subjects. The number of subjects with zero False Rejection Rate [FRR] was 44 and number of subjects with zero False Acceptance Rate [FAR] was 45. This paper addresses the computational load reduction in off-line signature verification based on minimal features using k-means, fuzzy k-means, k-nn, fuzzy k-nn and novel average-max approaches. FRR of 8.13% and FAR of 10% was achieved using k-nn classifier. The signature is a biometric, where variations in a genuine case, is a natural expectation. In the genuine signature, certain parts of signature vary from one instance to another. The system aims to provide simple, fast and robust system using less number of features when compared to state of art works.
Symmetry-breaking Answer Set Solving
Venue: arXiv cs.LO 2010
Year: 2010

In the context of Answer Set Programming, this paper investigates symmetry-breaking to eliminate symmetric parts of the search space and, thereby, simplify the solution process. We propose a reduction of disjunctive logic programs to a coloured digraph such that permutational symmetries can be constructed from graph automorphisms. Symmetries are then broken by introducing symmetry-breaking constraints. For this purpose, we formulate a preprocessor that integrates a graph automorphism system. Experiments demonstrate its computational impact.
An Efficient Network Coding based Retransmission Algorithm for Wireless Multicasts
Venue: arXiv cs.NI 2010
Year: 2010

Retransmission based on packet acknowledgement (ACK/NAK) is a fundamental error control technique employed in IEEE 802.11-2007 unicast network. However the 802.11-2007 standard falls short of proposing a reliable MAC-level recovery protocol for multicast frames. In this paper we propose a latency and bandwidth efficient coding algorithm based on the principles of network coding for retransmitting lost packets in a singlehop wireless multicast network and demonstrate its effectiveness over previously proposed network coding based retransmission algorithms.
Enhancing QOS and QOE in IMS enabled next generation networks
Venue: arXiv cs.NI 2010
Year: 2010

Managing network complexity, accommodating greater numbers of subscribers, improving coverage to support data services (e.g. email, video, and music downloads), keeping up to speed with fast-changing technology, and driving maximum value from existing networks - all while reducing CapEX and OpEX and ensuring Quality of Service (QoS) for the network and Quality of Experience (QoE) for the user. These are just some of the pressing business issues faced by mobileservice providers, summarized by the demand to "achieve more, for less." The ultimate goal of optimization techniques at the network and application layer is to ensure End-user perceived QoS. The next generation networks (NGN), a composite environment of proven telecommunications and Internet-oriented mechanisms have become generally recognized as the telecommunications environment of the future. However, the nature of the NGN environment presents several complex issues regarding quality assurance that have not existed in the legacy environments (e.g., multi-network, multi-vendor, and multi-operator IP-based telecommunications environment, distributed intelligence, third-party provisioning, fixed-wireless and mobile access, etc.). In this Research Paper, a service aware policy-based approach to NGN quality assurance is presented, taking into account both perceptual quality of experience and technologydependant quality of service issues. The respective procedures, entities, mechanisms, and profiles are discussed. The purpose of the presented approach is in research, development, and discussion of pursuing the end-to-end controllability of the quality of the multimedia NGN-based communications in an environment that is best effort in its nature and promotes end user's access agnosticism, service agility, and global mobility.
Providing content based billing architecture over Next Generation Network
Venue: arXiv cs.NI 2010
Year: 2010

Mobile Communication marketplace has stressed that "content is king" ever since the initial footsteps for Next Generation Networks like 3G, 3GPP, IP Multimedia subsystem (IMS) services. However, many carriers and content providers have struggled to drive revenue for content services, primarily due to current limitations of certain types of desirable content offerings, simplistic billing models, and the inability to support flexible pricing, charging and settlement. Unlike wire line carriers, wireless carriers have a limit to the volume of traffic they can carry, bounded by the finite wireless spectrum. Event based services like calling, conferencing etc., only perceive charge per event, while the Content based charging system attracts Mobile Network Operators (MNOs) to maximize service delivery to customer and achieve best ARPU. With the Next Generation Networks, the number of data related services that can be offered, is increased significantly. The wireless carrier will be able to move from offering wireless telecommunications services to offering wireless telecommunication services plus a number of personalized Value Added Services like news, games, video broadcasts, or multimedia messaging service (MMS) through the network. The next generation Content Based Billing systems allow the operators to maximize their revenues from such services. These systems will enable operators to offer and bill for application-based and content-based services, rather than for just bytes of data. Therefore, the wireless business focus is no longer on infrastructure build-outs but on customer retention and increased average revenue per customer (ARPU). The mobile operator generates new revenues, strengthens brand value, and differentiates its service to attract and retain customers.
Equational Characterization of Covariant-Contravariant Simulation and Conformance Simulation Semantics
Venue: arXiv cs.LO 2010
Year: 2010

Covariant-contravariant simulation and conformance simulation generalize plain simulation and try to capture the fact that it is not always the case that "the larger the number of behaviors, the better". We have previously studied their logical characterizations and in this paper we present the axiomatizations of the preorders defined by the new simulation relations and their induced equivalences. The interest of our results lies in the fact that the axiomatizations help us to know the new simulations better, understanding in particular the role of the contravariant characteristics and their interplay with the covariant ones; moreover, the axiomatizations provide us with a powerful tool to (algebraically) prove results of the corresponding semantics. But we also consider our results interesting from a metatheoretical point of view: the fact that the covariant-contravariant simulation equivalence is indeed ground axiomatizable when there is no action that exhibits both a covariant and a contravariant behaviour, but becomes non-axiomatizable whenever we have together actions of that kind and either covariant or contravariant actions, offers us a new subtle example of the narrow border separating axiomatizable and non-axiomatizable semantics. We expect that by studying these examples we will be able to develop a general theory separating axiomatizable and non-axiomatizable semantics.
An early warning method for crush
Venue: arXiv cs.MA 2010
Year: 2010

Fatal crush conditions occur in crowds with tragic frequency. Event organisers and architects are often criticised for failing to consider the causes and implications of crush, but the reality is that the prediction and mitigation of such conditions offers a significant technical challenge. Full treatment of physical force within crowd simulations is precise but computationally expensive; the more common method of human interpretation of results is computationally "cheap" but subjective and time-consuming. In this paper we propose an alternative method for the analysis of crowd behaviour, which uses information theory to measure crowd disorder. We show how this technique may be easily incorporated into an existing simulation framework, and validate it against an historical event. Our results show that this method offers an effective and efficient route towards automatic detection of crush.
The overlap number of a graph
Venue: arXiv cs.DM 2010
Year: 2010

An overlap representation is an assignment of sets to the vertices of a graph in such a way that two vertices are adjacent if and only if the sets assigned to them overlap. The overlap number of a graph is the minimum number of elements needed to form such a representation. We find the overlap numbers of cliques and complete bipartite graphs by relating the problem to previous research in combinatorics. The overlap numbers of paths, cycles, and caterpillars are also established. Finally, we show the NP-completeness of the problems of extending an overlap representation and finding a minimum overlap representation with limited containment.
Employer Expectations, Peer Effects and Productivity: Evidence from a Series of Field Experiments
Venue: arXiv cs.HC 2010
Year: 2010

This paper reports the results of a series of field experiments designed to investigate how peer effects operate in a real work setting. Workers were hired from an online labor market to perform an image-labeling task and, in some cases, to evaluate the work product of other workers. These evaluations had financial consequences for both the evaluating worker and the evaluated worker. The experiments showed that on average, evaluating high-output work raised an evaluator's subsequent productivity, with larger effects for evaluators that are themselves highly productive. The content of the subject evaluations themselves suggest one mechanism for peer effects: workers readily punished other workers whose work product exhibited low output/effort. However, non-compliance with employer expectations did not, by itself, trigger punishment: workers would not punish non-complying workers so long as the evaluated worker still exhibited high effort. A worker's willingness to punish was strongly correlated with their own productivity, yet this relationship was not the result of innate differences---productivity-reducing manipulations also resulted in reduced punishment. Peer effects proved hard to stamp out: although most workers complied with clearly communicated maximum expectations for output, some workers still raised their production beyond the output ceiling after evaluating highly productive yet non-complying work products.
A Case Study in Matching Service Descriptions to Implementations in an Existing System
Venue: arXiv cs.SE 2010
Year: 2010

A number of companies are trying to migrate large monolithic software systems to Service Oriented Architectures. A common approach to do this is to first identify and describe desired services (i.e., create a model), and then to locate portions of code within the existing system that implement the described services. In this paper we describe a detailed case study we undertook to match a model to an open-source business application. We describe the systematic methodology we used, the results of the exercise, as well as several observations that throw light on the nature of this problem. We also suggest and validate heuristics that are likely to be useful in partially automating the process of matching service descriptions to implementations.
Low ML Decoding Complexity STBCs via Codes over GF(4)
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we give a new framework for constructing low ML decoding complexity Space-Time Block Codes (STBCs) using codes over the finite field $\mathbb{F}_4$. Almost all known low ML decoding complexity STBCs can be obtained via this approach. New full-diversity STBCs with low ML decoding complexity and cubic shaping property are constructed, via codes over $\mathbb{F}_4$, for number of transmit antennas \mbox{$N=2^m$}, \mbox{$m \geq 1$}, and rates \mbox{$R>1$} complex symbols per channel use. When \mbox{$R=N$}, the new STBCs are information-lossless as well. The new class of STBCs have the least known ML decoding complexity among all the codes available in the literature for a large set of \mbox{$(N,R)$} pairs.
An Empirical Study on Content Bundling in BitTorrent Swarming System
Venue: arXiv cs.NI 2010
Year: 2010

Despite the tremendous success of BitTorrent, its swarming system suffers from a fundamental limitation: lower or no availability of unpopular contents. Recently, Menasche et al. has shown that bundling is a promising solution to mitigate this availability problem; it improves the availability and reduces download times for unpopular contents by combining multiple files into a single swarm. There also have been studies on bundling strategies and performance issues in bundled swarms. In spite of the recent surge of interest in the benefits of and strategies for bundling, there are still little empirical grounding for understanding, describing, and modeling it. This is the first empirical study that measures and analyzes how prevalent contents bundling is in BitTorrent and how peers access the bundled contents, in comparison to the other non-bundled (i.e., single-filed) ones. To our surprise, we found that around 70% of BitTorrent swarms contain multiple files, which indicate that bundling has become widespread for contents sharing. We also show that the amount of bytes shared in bundled swarms is estimated to be around 85% out of all the BitTorrent contents logged in our datasets. Inspired from our findings, we raise and discuss three important research questions in the field of file sharing systems as well as future contents-oriented networking: i) bundling strategies, ii) bundling-aware sharing systems in BitTorrent, and iii) implications on content-oriented networking.
Fastest Mixing Markov Chain on Symmetric K-Partite Network
Venue: arXiv cs.DM 2010
Year: 2010

Solving fastest mixing Markov chain problem (i.e. finding transition probabilities on the edges to minimize the second largest eigenvalue modulus of the transition probability matrix) over networks with different topologies is one of the primary areas of research in the context of computer science and one of the well known networks in this issue is K-partite network. Here in this work we present analytical solution for the problem of fastest mixing Markov chain by means of stratification and semidefinite programming, for four particular types of K-partite networks, namely Symmetric K-PPDR, Semi Symmetric K-PPDR, Cycle K-PPDR and Semi Cycle K-PPDR networks. Our method in this paper is based on convexity of fastest mixing Markov chain problem, and inductive comparing of the characteristic polynomials initiated by slackness conditions in order to find the optimal transition probabilities. The presented results shows that a Symmetric K-PPDR network and its equivalent Semi Symmetric K-PPDR network have the same SLEM despite the fact that Semi symmetric K-PPDR network has less edges than its equivalent symmetric K-PPDR network and at the same time symmetric K-PPDR network has better mixing rate per step than its equivalent semi symmetric K-PPDR network at first few iterations. The same results are true for Cycle K-PPDR and Semi Cycle K-PPDR networks. Also the obtained optimal transition probabilities have been compared with the transition probabilities obtained from Metropolis-Hasting method by comparing mixing time improvements numerically.
On BICM receivers for TCM transmission
Venue: arXiv cs.IT 2010
Year: 2010

Recent results have shown that the performance of bit-interleaved coded modulation (BICM) using convolutional codes in nonfading channels can be significantly improved when the interleaver takes a trivial form (BICM-T), i.e., when it does not interleave the bits at all. In this paper, we give a formal explanation for these results and show that BICM-T is in fact the combination of a TCM transmitter and a BICM receiver. To predict the performance of BICM-T, a new type of distance spectrum for convolutional codes is introduced, analytical bounds based on this spectrum are developed, and asymptotic approximations are also presented. It is shown that the minimum distance of the code is not the relevant optimization criterion for BICM-T. Optimal convolutional codes for different constrain lengths are tabulated and asymptotic gains of about 2 dB are obtained. These gains are found to be the same as those obtained by Ungerboeck's one-dimensional trellis coded modulation (1D-TCM), and therefore, in nonfading channels, BICM-T is shown to be asymptotically as good as 1D-TCM.
Bidirectional multi-pair network with a MIMO relay: Beamforming strategies and lack of duality
Venue: arXiv cs.IT 2010
Year: 2010

We address the problem of a multi-user relay network, where multiple single-antenna node pairs want to exchange information by using a multiple antenna relay node. Due to the half-duplex constraint of the relay, the exchange of information takes place in two steps. In the first step, the nodes transmit their data to the relay, while in the second step, the relay is broadcasting the data by using linear and non-linear precoding strategies. We focus on the second step in this paper. We first consider the problem of maximizing the overall rate achievable using linear and dirty-paper type precoding strategies at the relay. Then, we consider minimizing the total power at the relay subject to individual SINR constraints using the same strategies at the relay. We show that the downlink-uplink duality does not hold for the setup considered here, which is a somewhat surprising result. We also show that the beamforming strategy which is optimal in the single-pair case performs very well in the multi-pair case for practically relevant SNR. The results are illustrated by numerical simulations.