OpenRaiser/Intern-Atlas huggingface dataset:
Thinking Twice about Second-Price Ad Auctions
Venue: arXiv cs.DS 2008
Year: 2008

Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that pricing is done via a first-price auction. This does not realistically model the Generalized Second Price (GSP) auction used in practice, in which bidders pay the next-highest bid for keywords that they are allocated. Towards the goal of more realistically modeling these auctions, we introduce the Second-Price Ad Auctions problem, in which bidders' payments are determined by the GSP mechanism. We show that the complexity of the Second-Price Ad Auctions problem is quite different than that of the more studied First-Price Ad Auctions problem. First, unlike the first-price variant, for which small constant-factor approximations are known, it is NP-hard to approximate the Second-Price Ad Auctions problem to any non-trivial factor, even when the bids are small compared to the budgets. Second, this discrepancy extends even to the 0-1 special case that we call the Second-Price Matching problem (2PM). Offline 2PM is APX-hard, and for online 2PM there is no deterministic algorithm achieving a non-trivial competitive ratio and no randomized algorithm achieving a competitive ratio better than 2. This contrasts with the results for the analogous special case in the first-price model, the standard bipartite matching problem, which is solvable in polynomial time and which has deterministic and randomized online algorithms achieving better competitive ratios. On the positive side, we provide a 2-approximation for offline 2PM and a 5.083-competitive randomized algorithm for online 2PM. The latter result makes use of a new generalization of a result on the performance of the "Ranking" algorithm for online bipartite matching.
Randomized Distributed Configuration Management of Wireless Networks: Multi-layer Markov Random Fields and Near-Optimality
Venue: arXiv cs.DC 2008
Year: 2008

Distributed configuration management is imperative for wireless infrastructureless networks where each node adjusts locally its physical and logical configuration through information exchange with neighbors. Two issues remain open. The first is the optimality. The second is the complexity. We study these issues through modeling, analysis, and randomized distributed algorithms. Modeling defines the optimality. We first derive a global probabilistic model for a network configuration which characterizes jointly the statistical spatial dependence of a physical- and a logical-configuration. We then show that a local model which approximates the global model is a two-layer Markov Random Field or a random bond model. The complexity of the local model is the communication range among nodes. The local model is near-optimal when the approximation error to the global model is within a given error bound. We analyze the trade-off between an approximation error and complexity, and derive sufficient conditions on the near-optimality of the local model. We validate the model, the analysis and the randomized distributed algorithms also through simulation.
Algorithms for Locating Constrained Optimal Intervals
Venue: arXiv cs.DS 2008
Year: 2008

In this work, we obtain the following new results. 1. Given a sequence $D=((h_1,s_1), (h_2,s_2) ..., (h_n,s_n))$ of number pairs, where $s_i>0$ for all $i$, and a number $L_h$, we propose an O(n)-time algorithm for finding an index interval $[i,j]$ that maximizes $\frac{\sum_{k=i}^{j} h_k}{\sum_{k=i}^{j} s_k}$ subject to $\sum_{k=i}^{j} h_k \geq L_h$. 2. Given a sequence $D=((h_1,s_1), (h_2,s_2) ..., (h_n,s_n))$ of number pairs, where $s_i=1$ for all $i$, and an integer $L_s$ with $1\leq L_s\leq n$, we propose an $O(n\frac{T(L_s^{1/2})}{L_s^{1/2}})$-time algorithm for finding an index interval $[i,j]$ that maximizes $\frac{\sum_{k=i}^{j} h_k}{\sqrt{\sum_{k=i}^{j} s_k}}$ subject to $\sum_{k=i}^{j} s_k \geq L_s$, where $T(n')$ is the time required to solve the all-pairs shortest paths problem on a graph of $n'$ nodes. By the latest result of Chan \cite{Chan}, $T(n')=O(n'^3 \frac{(\log\log n')^3}{(\log n')^2})$, so our algorithm runs in subquadratic time $O(nL_s\frac{(\log\log L_s)^3}{(\log L_s)^2})$.
Relay vs. User Cooperation in Time-Duplexed Multiaccess Networks
Venue: arXiv cs.IT 2008
Year: 2008

The performance of user-cooperation in a multi-access network is compared to that of using a wireless relay. Using the total transmit and processing power consumed at all nodes as a cost metric, the outage probabilities achieved by dynamic decode-and-forward (DDF) and amplify-and-forward (AF) are compared for the two networks. A geometry-inclusive high signal-to-noise ratio (SNR) outage analysis in conjunction with area-averaged numerical simulations shows that user and relay cooperation achieve a maximum diversity of K and 2 respectively for a K-user multiaccess network under both DDF and AF. However, when accounting for energy costs of processing and communication, relay cooperation can be more energy efficient than user cooperation, i.e., relay cooperation achieves coding (SNR) gains, particularly in the low SNR regime, that override the diversity advantage of user cooperation.
Random Linear Network Coding For Time Division Duplexing: When To Stop Talking And Start Listening
Venue: arXiv cs.IT 2008
Year: 2008

A new random linear network coding scheme for reliable communications for time division duplexing channels is proposed. The setup assumes a packet erasure channel and that nodes cannot transmit and receive information simultaneously. The sender transmits coded data packets back-to-back before stopping to wait for the receiver to acknowledge (ACK) the number of degrees of freedom, if any, that are required to decode correctly the information. We provide an analysis of this problem to show that there is an optimal number of coded data packets, in terms of mean completion time, to be sent before stopping to listen. This number depends on the latency, probabilities of packet erasure and ACK erasure, and the number of degrees of freedom that the receiver requires to decode the data. This scheme is optimal in terms of the mean time to complete the transmission of a fixed number of data packets. We show that its performance is very close to that of a full duplex system, while transmitting a different number of coded packets can cause large degradation in performance, especially if latency is high. Also, we study the throughput performance of our scheme and compare it to existing half-duplex Go-back-N and Selective Repeat ARQ schemes. Numerical results, obtained for different latencies, show that our scheme has similar performance to the Selective Repeat in most cases and considerable performance gain when latency and packet error probability is high.
A fast approach for overcomplete sparse decomposition based on smoothed L0 norm
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined Sparse Component Analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the L1 norm using Linear Programming (LP) techniques, our algorithm tries to directly minimize the L0 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.
Frequent itemsets mining for database auto-administration
Venue: arXiv cs.DB 2008
Year: 2008

With the wide development of databases in general and data warehouses in particular, it is important to reduce the tasks that a database administrator must perform manually. The aim of auto-administrative systems is to administrate and adapt themselves automatically without loss (or even with a gain) in performance. The idea of using data mining techniques to extract useful knowledge for administration from the data themselves has existed for some years. However, little research has been achieved. This idea nevertheless remains a very promising approach, notably in the field of data warehousing, where queries are very heterogeneous and cannot be interpreted easily. The aim of this study is to search for a way of extracting useful knowledge from stored data themselves to automatically apply performance optimization techniques, and more particularly indexing techniques. We have designed a tool that extracts frequent itemsets from a given workload to compute an index configuration that helps optimizing data access time. The experiments we performed showed that the index configurations generated by our tool allowed performance gains of 15% to 25% on a test database and a test data warehouse.
Expressing OLAP operators with the TAX XML algebra
Venue: arXiv cs.DB 2008
Year: 2008

With the rise of XML as a standard for representing business data, XML data warehouses appear as suitable solutions for Web-based decision-support applications. In this context, it is necessary to allow OLAP analyses over XML data cubes (XOLAP). Thus, XQuery extensions are needed. To help define a formal framework and allow much-needed performance optimizations on analytical queries expressed in XQuery, having an algebra at one's disposal is desirable. However, XOLAP approaches and algebras from the literature still largely rely on the relational model and/or only feature a small number of OLAP operators. In opposition, we propose in this paper to express a broad set of OLAP operators with the TAX XML algebra.
Single source shortest paths in $H$-minor free graphs
Venue: arXiv cs.DS 2008
Year: 2008

We present an algorithm for the Single Source Shortest Paths (SSSP) problem in \emph{$H$-minor free} graphs. For every fixed $H$, if $G$ is a graph with $n$ vertices having integer edge lengths and $s$ is a designated source vertex of $G$, the algorithm runs in $\tilde{O}(n^{\sqrt{11.5}-2} \log L) \le O(n^{1.392} \log L)$ time, where $L$ is the absolute value of the smallest edge length. The algorithm computes shortest paths and the distances from $s$ to all vertices of the graph, or else provides a certificate that $G$ is not $H$-minor free. Our result improves an earlier $O(n^{1.5} \log L)$ time algorithm for this problem, which follows from a general SSSP algorithm of Goldberg.
Kinetostatic Performance of a Planar Parallel Mechanism with Variable Actuation
Venue: arXiv cs.RO 2008
Year: 2008

This paper deals with a new planar parallel mechanism with variable actuation and its kinetostatic performance. A drawback of parallel mechanisms is the non homogeneity of kinetostatic performance within their workspace. The common approach to solve this problem is the introduction of actuation redundancy, that involves force control algorithms. Another approach, highlighted in this paper, is to select the actuated joint in each limb with regard to the pose of the end-effector. First, the architecture of the mechanism and two kinetostatic performance indices are described. Then, the actuating modes of the mechanism are compared.
Supervised Dictionary Learning
Venue: arXiv cs.CV 2008
Year: 2008

It is now well established that sparse signal models are well suited to restoration tasks and can effectively be learned from audio, image, and video data. Recent research has been aimed at learning discriminative sparse models instead of purely reconstructive ones. This paper proposes a new step in that direction, with a novel sparse representation for signals belonging to different classes in terms of a shared dictionary and multiple class-decision functions. The linear variant of the proposed model admits a simple probabilistic interpretation, while its most general variant admits an interpretation in terms of kernels. An optimization framework for learning all the components of the proposed model is presented, along with experimental results on standard handwritten digit and texture classification tasks.
Monadic Datalog over Finite Structures with Bounded Treewidth
Venue: arXiv cs.DB 2008
Year: 2008

Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know: Any property of finite structures, which is expressible by an MSO sentence, can be decided in linear time (data complexity) if the structures have bounded treewidth. In principle, Courcelle's Theorem can be applied directly to construct concrete algorithms by transforming the MSO evaluation problem into a tree language recognition problem. The latter can then be solved via a finite tree automaton (FTA). However, this approach has turned out to be problematical, since even relatively simple MSO formulae may lead to a ``state explosion'' of the FTA. In this work we propose monadic datalog (i.e., datalog where all intentional predicate symbols are unary) as an alternative method to tackle this class of fixed-parameter tractable problems. We show that if some property of finite structures is expressible in MSO then this property can also be expressed by means of a monadic datalog program over the structure plus the tree decomposition. Moreover, we show that the resulting fragment of datalog can be evaluated in linear time (both w.r.t. the program size and w.r.t. the data size). This new approach is put to work by devising new algorithms for the 3-Colorability problem of graphs and for the PRIMALITY problem of relational schemas (i.e., testing if some attribute in a relational schema is part of a key). We also report on experimental results with a prototype implementation.
Kinematic and Dynamic Analyses of the Orthoglide 5-axis
Venue: arXiv cs.RO 2008
Year: 2008

This paper deals with the kinematic and dynamic analyses of the Orthoglide 5-axis, a five-degree-of-freedom manipulator. It is derived from two manipulators: i) the Orthoglide 3-axis; a three dof translational manipulator and ii) the Agile eye; a parallel spherical wrist. First, the kinematic and dynamic models of the Orthoglide 5-axis are developed. The geometric and inertial parameters of the manipulator are determined by means of a CAD software. Then, the required motors performances are evaluated for some test trajectories. Finally, the motors are selected in the catalogue from the previous results.
Criteria on Utility Designing of Convex Optimization in FDMA Networks
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, we investigate the network utility maximization problem in FDMA systems. We summarize with a suite of criteria on designing utility functions so as to achieve the global optimization convex. After proposing the general form of the utility functions, we present examples of commonly used utility function forms that are consistent with the criteria proposed in this paper, which include the well-known proportional fairness function and the sigmoidal-like functions. In the second part of this paper, we use numerical results to demonstrate a case study based on the criteria mentioned above, which deals with the subcarrier scheduling problem with dynamic rate allocation in FDMA system.
Distributed Spiral Optimization in Wireless Sensor Networks without Fusion Centers
Venue: arXiv cs.NI 2008
Year: 2008

A distributed spiral algorithm for distributed optimization in WSN is proposed. By forming a spiral-shape message passing scheme among clusters, without loss of estimation accuracy and convergence speed, the algorithm is proved to converge with a lower total transport cost than the distributed in-cluster algorithm.
A Heuristic Scheduling Scheme in Multiuser OFDMA Networks
Venue: arXiv cs.NI 2008
Year: 2008

Conventional heterogeneous-traffic scheduling schemes utilize zero-delay constraint for real-time services, which aims to minimize the average packet delay among real-time users. However, in light or moderate load networks this strategy is unnecessary and leads to low data throughput for non-real-time users. In this paper, we propose a heuristic scheduling scheme to solve this problem. The scheme measures and assigns scheduling priorities to both real-time and non-real-time users, and schedules the radio resources for the two user classes simultaneously. Simulation results show that the proposed scheme efficiently handles the heterogeneous-traffic scheduling with diverse QoS requirements and alleviates the unfairness between real-time and non-real-time services under various traffic loads.
Performance Comparison of Cooperative and Distributed Spectrum Sensing in Cognitive Radio
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, we compare the performances of cooperative and distributed spectrum sensing in wireless sensor networks. After introducing the basic problem, we describe two strategies: 1) a cooperative sensing strategy, which takes advantage of cooperation diversity gain to increase probability of detection and 2) a distributed sensing strategy, which by passing the results in an inter-node manner increases energy efficiency and fairness among nodes. Then, we compare the performances of the strategies in terms of three criteria: agility, energy efficiency, and robustness against SNR changes, and summarize the comparison. It shows that: 1) the non-cooperative strategy has the best fairness of energy consumption, 2) the cooperative strategy leads to the best agility, and 3) the distributed strategy leads to the lowest energy consumption and the best robustness against SNR changes.
The Approximate Capacity of the Many-to-One and One-to-Many Gaussian Interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

Recently, Etkin, Tse, and Wang found the capacity region of the two-user Gaussian interference channel to within one bit/s/Hz. A natural goal is to apply this approach to the Gaussian interference channel with an arbitrary number of users. We make progress towards this goal by finding the capacity region of the many-to-one and one-to-many Gaussian interference channels to within a constant number of bits. The result makes use of a deterministic model to provide insight into the Gaussian channel. The deterministic model makes explicit the dimension of signal scale. A central theme emerges: the use of lattice codes for alignment of interfering signals on the signal scale.
Revisiting the Panko-Halverson Taxonomy of Spreadsheet Errors
Venue: arXiv cs.SE 2008
Year: 2008

The purpose of this paper is to revisit the Panko-Halverson taxonomy of spreadsheet errors and suggest revisions. There are several reasons for doing so: First, the taxonomy has been widely used. Therefore, it should have scrutiny; Second, the taxonomy has not been widely available in its original form and most users refer to secondary sources. Consequently, they often equate the taxonomy with the simplified extracts used in particular experiments or field studies; Third, perhaps as a consequence, most users use only a fraction of the taxonomy. In particular, they tend not to use the taxonomy's life-cycle dimension; Fourth, the taxonomy has been tested against spreadsheets in experiments and spreadsheets in operational use. It is time to review how it has fared in these tests; Fifth, the taxonomy was based on the types of spreadsheet errors that were known to the authors in the mid-1990s. Subsequent experience has shown that the taxonomy needs to be extended for situations beyond those original experiences; Sixth, the omission category in the taxonomy has proven to be too narrow. Although this paper will focus on the Panko-Halverson taxonomy, this does not mean that that it is the only possible error taxonomy or even the best error taxonomy.
Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability
Venue: arXiv cs.CC 2008
Year: 2008

We prove that the directed graph reachability problem (transitive closure) can be solved by monotone fan-in 2 boolean circuits of depth (1/2+o(1))(log n)^2, where n is the number of nodes. This improves the previous known upper bound (1+o(1))(log n)^2. The proof is non-constructive, but we give a constructive proof of the upper bound (7/8+o(1))(log n)^2.
Multiprocessor Global Scheduling on Frame-Based DVFS Systems
Venue: arXiv cs.OS 2008
Year: 2008

In this ongoing work, we are interested in multiprocessor energy efficient systems, where task durations are not known in advance, but are know stochastically. More precisely, we consider global scheduling algorithms for frame-based multiprocessor stochastic DVFS (Dynamic Voltage and Frequency Scaling) systems. Moreover, we consider processors with a discrete set of available frequencies.
Block Network Error Control Codes and Syndrome-based Complete Maximum Likelihood Decoding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, network error control coding is studied for robust and efficient multicast in a directed acyclic network with imperfect links. The block network error control coding framework, BNEC, is presented and the capability of the scheme to correct a mixture of symbol errors and packet erasures and to detect symbol errors is studied. The idea of syndrome-based decoding and error detection is introduced for BNEC, which removes the effect of input data and hence decreases the complexity. Next, an efficient three-stage syndrome-based BNEC decoding scheme for network error correction is proposed, in which prior to finding the error values, the position of the edge errors are identified based on the error spaces at the receivers. In addition to bounded-distance decoding schemes for error correction up to the refined Singleton bound, a complete decoding scheme for BNEC is also introduced. Specifically, it is shown that using the proposed syndrome-based complete decoding, a network error correcting code with redundancy order d for receiver t, can correct d-1 random additive errors with a probability sufficiently close to 1, if the field size is sufficiently large. Also, a complete maximum likelihood decoding scheme for BNEC is proposed. As the probability of error in different network edges is not equal in general, and given the equivalency of certain edge errors within the network at a particular receiver, the number of edge errors, assessed in the refined Singleton bound, is not a sufficient statistic for ML decoding.
Content Sharing for Mobile Devices
Venue: arXiv cs.DC 2008
Year: 2008

The miniaturisation of computing devices has seen computing devices become increasingly pervasive in society. With this increased pervasiveness, the technologies of small computing devices have also improved. Mobile devices are now capable of capturing various forms of multimedia and able to communicate wirelessly using increasing numbers of communication techniques. The owners and creators of local content are motivated to share this content in ever increasing volume; the conclusion has been that social networks sites are seeing a revolution in the sharing of information between communities of people. As load on centralised systems increases, we present a novel decentralised peer-to-peer approach dubbed the Market Contact Protocol (MCP) to achieve cost effective, scalable and efficient content sharing using opportunistic networking (pocket switched networking), incentive, context-awareness, social contact and mobile devices. Within the report we describe how the MCP is simulated with a superimposed geographic framework on top of the JiST (Java in Simulation Time) framework to evaluate and measure its capability to share content between massively mobile peers. The MCP is shown in conclusion to be a powerful means by which to share content in a massively mobile ad-hoc environment.