53242714
Network design with weighted players
We consider a model of game-theoretic network design initially studied by Anshelevich et al. [2], where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided by the number of players using it. In this special case, Anshelevich et al. [2] proved that pure-strategy Nash equilibria always exist and that the price of stability--the ratio in costs of a minimumcost Nash equilibrium and an optimal solution--is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight wi ≥ 1, and its cost share of an edge in its path equals wi times the edge cost, divided by the total weight of the players using the edge.This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria--outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log wmax)-approximate Nash equilibria exist in all weighted Shapley network design games, where wmax is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability and low cost: for every α = Ω(log wmax), the price of stability with respect to O(α)- approximate Nash equilibria is O((log W)/α), where W is the sum of the players' weights. In particular, there is always an O(logW)-approximate Nash equilibrium with cost within a constant factor of optimal.Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log wmax/ log log wmax)-approximate Nash equilibria, and show that for all α = Ω(logwmax/ log log wmax), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor.
13538048
Error Free Self-assembly Using Error Prone Tiles
DNA self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. In nature, DNA self-assembly is often equipped with explicit mechanisms for both error prevention and error correction. For artificial self-assembly, these problems are even more important since we are interested in assembling large systems with great precision. 
 
We present an error-correction scheme, called snaked proof-reading, which can correct both growth and nucleation errors in a self-assembling system. This builds upon an earlier construction of Winfree and Bekbolatov [11], which could correct a limited class of growth errors. Like their construction, our system also replaces each tile in the system by a k × k block of tiles, and does not require changing the basic tile assembly model proposed by Rothemund and Winfree [8]. 
 
We perform a theoretical analysis of our system under fairly general assumptions: tiles can both attach and fall off depending on the thermodynamic rate parameters which also govern the error rate. We prove that with appropriate values of the block size, a seed row of n tiles can be extended into an n × n square of tiles without errors in expected time $\widetilde{O}(n)$, and further, this square remains stable for an expected time of $\widetilde{\Omega}(n)$. This is the first error-correction system for DNA self-assembly that has provably good assembly time (close to linear) and provable error-correction. The assembly time is thesame, up to logarithmic factors, as the time for an irreversible, error-free assembly. 
 
We also did a preliminary simulation study of our scheme. In simulations, our scheme performs much better (in terms of error-correction) than the earlier scheme of Winfree and Bekbolatov, and also much better than the unaltered tile system. 
 
Our basic construction (and analysis) applies to all rectilinear tile systems (where growth happens from south to north and west to east). These systems include the Sierpinski tile system, the square-completion tile system, and the block cellular automata for simulating Turing machines. It also applies to counters, a basic primitive in many self-assembly constructions and computations.
9752024
Invadable self-assembly: combining robustness with efficiency
DNA self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. In nature, DNA self-assembly is often equipped with explicit mechanisms for both error prevention and error correction. For artificial self-assembly, these problems are even more important since we are interested in assembling large systems with great precision. So far, theoretical studies of DNA self-assembly have primarily focused on the efficiency of the assembly process in terms of the program size and the running time. In this paper, we perform a preliminary study of algorithms for DNA self-assembly that are both robust and efficient.Strand invasion is an important error-correction mechanism observed in several natural self-assembling systems. We first define invadable self-assemblies as self-assembling systems which can effectively use the strand invasion mechanism for error-correction. We then show that O(log2 n/ log log n) tiles are sufficient to assemble an n × n square in this model. The running time of our system is Õ (n). We obtain our result by growing a counter which simulates Chinese remaindering. The running time and the program size of our invadable system are within polylogarithmic factors of known lower bounds for general systems, i.e. the efficiency penalty for obtaining robustness is small in our model. We also show how to simulate an arbitrary Turing machine using an invadable self-assembly system.
20735579
Kinetically stable task assignment for networks of microservers
• Job titles for all employees • Most recent payroll data (wages, hours, job codes, and dates of hire) • Union contracts • Employee handbooks or benefit descriptions • Summary plan descriptions for health and retirement plans • Benefit costs summaries or insurance bills For a detailed listing of information that BLS economists typically request, please visit the National Compensation Survey Web site at http://www.bls.gov/ncs/collection.htm. What is the National Compensation Survey (NCS)?
7717458
From requirements negotiation to software architecture decisions
Architecture design and requirements negotiations are conceptually tightly related but often performed separately in real-world software development projects. As our prior case studies have revealed, this separation causes uncertainty in requirements negotiation that hinders progress, limits the success of architecture design, and often leads to wasted effort and substantial re-work later in the development life-cycle. Explicit requirements elicitation and negotiation is needed to be able to appropriately consider and evaluate architecture alternatives and the architecture alternatives need be understood during requirements negotiation. This paper propose the WinCBAM framework, extending an architecture design method, called cost benefit analysis method (CBAM) framework to include an explicit requirements negotiation component based on the WinWin methodology. We then provide a retrospective case study that demonstrates the use of the WinCBAM. We show that the integrated method is substantially more powerful than the WinWin and CBAM methods performed separately. The integrated method can assist stakeholders to elicit, explore, evaluate, negotiate, and agree upon software architecture alternatives based on each of their requirement Win conditions. By understanding the architectural implication of requirements they can be negotiated more successfully: potential requirements conflicts can be discovered or alleviated relatively early in the development life-cycle.
2098964
Spam double-funnel: connecting web spammers with advertisers
Spammers use questionable search engine optimization (SEO) techniques to promote their spam links into top search results. In this paper, we focus on one prevalent type of spam - redirection spam - where one can identify spam pages by the third-party domains that these pages redirect traffic to. We propose a five-layer, double-funnel model for describing end-to-end redirection spam, present a methodology for analyzing the layers, and identify prominent domains on each layer using two sets of commercial keywords. one targeting spammers and the other targeting advertisers. The methodology and findings are useful for search engines to strengthen their ranking algorithms against spam, for legitimate website owners to locate and remove spam doorway pages, and for legitimate advertisers to identify unscrupulous syndicators who serve ads on spam pages.
19964958
Near-optimal data allocation over multiple broadcast channels
Data broadcast is known as a scalable way to transmit database items to large client populations through a wireless channel. However, with a large set of items, the expected delay of receiving desired data increases due to the sequential nature of the broadcast channel. One possible solution is to increase the number of available channels and allocate items evenly over these channels, then cyclically broadcast data in each channel. In view of data access skew (the access frequencies of data are usually different), some channels may be reserved exclusively for those few frequently requested items, while the infrequently accessed bulk of data are allocated on other channels. In this paper, an O(N log K) restricted dynamic programming (RDP) algorithm is proposed to partition N items over K channels assuming data access is skewed with the object of minimizing the average expected delay (aed) of clients. To speed up the DP process, for any partition, we predict a possible location which may be very close to the optimal cut by using a low bound as the actual aed for the remaining items. Thus, the number of comparisons in DP can be restricted to a small interval around the predicted cut point. To further reduce the costs in DP, the hierarchical property of optimal solution is adopted. Simulation results show that, the hit rate obtained by RDP is higher than 90% and it also outperforms the existing algorithm 200%. We extend the work of RDP and develop an O(N log N log K) PKR algorithm; simulation results show that the solution is optimal.
14259579
FTXI: fault tolerance XCS in integer
In the realm of data mining, several key issues exists in the traditional classification algorithms, such as low readability, large rule number, and low accuracy with information losing. In this paper, we propose a new classification methodology, called fault tolerance XCS in integer (FTXI), by extending XCS to handle conditions in integers and integrating the mechanism of fault tolerance in the context of data mining into the framework of XCS. We also design and generate appropriate artificial data sets for examining and verifying the proposed method. Our experiments indicate that FTXI can provide the least rule number, obtain high prediction accuracy, and offer rule readability, compared to C4.5 and XCS in integer without fault tolerance.
8882088
Design of Nearest Neighbor Classifiers Using an Intelligent Multi-objective Evolutionary Algorithm
The goal of designing optimal nearest neighbor classifiers is to maximize classification accuracy while minimizing the sizes of both reference and feature sets. A usual way is to adaptively weight the three objectives as an objective function and then use a single-objective optimization method for achieving this goal. This paper proposes a multi-objective approach to cope with the weight tuning problem for practitioners. A novel intelligent multi-objective evolutionary algorithm IMOEA is utilized to simultaneously edit compact reference and feature sets for nearest neighbor classification. Two comparison studies are designed to evaluate performance of the proposed approach. It is shown empirically that the IMOEA-designed classifiers have high classification accuracy and small sizes of reference and feature sets. Moreover, IMOEA can provide a set of good solutions for practitioners to choose from in a single run. The simulation results indicate that the IMOEA-based approach is an expedient method to design nearest neighbor classifiers, compared with an existing single- objective approach.