37302257
On Maximum Symmetric Subgraphs
Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting dges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an O(log n)-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem.
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)?
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.
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.
10326556
Orthogonal and Straight-Line Drawings of Graphs with Succinct Representations
The concept of a hierarchical design has played an important role in various areas of computer science and engineering, including software engineering, CAD, among others. Graphs with hierarchical structures, which are capable of describing large-scale regular structures in a succinct manner, have naturally become an interesting and important modeling tool for facilitating such a hierarchical design. In the literature, a number of succinct models for representing graphs with hierarchical structures have been proposed. See, e.g., [4,5]. In each of such hierarchical graph models, a succinct description is capable of representing a graph (which can be thought of as the expansion of the description) whose size is exponential in the length of the description.
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.
8713624
Intelligent agents meet semantic web in a smart meeting room
We describe a new smart meeting room system called EasyMeeting that explores the use of FIPA agent technologies, Semantic Web ontologies, logic reasoning, and security and privacy policies. Building on a pervasive computing system that we have developed previously, EasyMeeting can provide relevant services and information to meeting participants based on their situational needs. Our system exploits the context-aware support provided by the Context Broker Architecture (CoBrA). Central to CoBrA is an intelligent broker agent that maintains a shared model of context for all computing entities in the space and enforces the privacy policies defined by the users. We also describe the use of CoBrA ontologies, logic reasoning, and privacy protection mechanisms, and evaluate our initial user experience studies.
10922325
Quantified Constraint Satisfaction and Bounded Treewidth
Because the constraint satisfaction problem (CSP) is in general intractable, restricted cases of the CSP that are polynomial-time tractable have been heavily sought after. One class of restrictions that has been studied are variable-based restrictions, which concern the interaction among variables. In this paper, we consider the quantified constraint satisfaction problem (QCSP), a framework more general than the CSP. We present a QCSP tractability result arising from variable-based restrictions by giving a polynomial time algorithm for certain classes of QCSP instances having bounded treewidth.
14045822
Optimizing search by showing results in context
We developed and evaluated seven interfaces for integrating semantic category information with Web search results. List interfaces were based on the familiar ranked-listing of search results, sometimes augmented with a category name for each result. Category interfaces also showed page titles and/or category names, but re-organized the search results so that items in the same category were grouped together visually. Our user studies show that all Category interfaces were more effective than List interfaces even when lists were augmented with category names for each result. The best category performance was obtained when both category names and individual page titles were presented. Either alone is better than a list presentation, but both together provide the most effective means for allowing users to quickly examining search results. These results provide a better understanding of the perceptual and cognitive factors underlying the advantage of category groupings and provide some practical guidance to Web search interface designers.
1567676
Bringing order to the Web: automatically categorizing search results
We developed a user interface that organizes Web search results into hierarchical categories. Text classification algorithms were used to automatically classify arbitrary search results into an existing category structure on-the-fly. A user study compared our new category interface with the typical ranked list interface of search results. The study showed that the category interface is superior both in objective and subjective measures. Subjects liked the category interface much better than the list interface, and they were 50% faster at finding information that was organized into categories. Organizing search results allows users to focus on items in categories of interest rather than having to browse through all the results sequentially.
9860639
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
It is well known 9] that nding a maximal independent set in a graph is in class N C, and 10] that nding a maximal independent set in a hypergraph with xed dimension is in RN C. It is not known whether this latter problem remains in N C when the dimension is part of the input. We will study the problem when the problem instances are randomly chosen. It was shown in 6] that the expected running time of a simple parallel algorithm for nding the lexicographically rst maximal independent set (lfmis) in a random simple graph is logarithmic in the input size. In this paper, we will prove a generalization of this result. We show that if a random k-uniform hypergraph has vertex set f1; 2; : : : ; ng and its edges are chosen independently with probability p from the set of ? n k possible edges, then our algorithm nds the lfmis