15338297
Fast construction of overlay networks
An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying network, but each participating node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay networks such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree <i>d</i> and the length of a node identifier is <i>W</i>, the mechanism constructs a binary search tree of nodes of depth <i>O</i>(<i>W</i>) in expected <i>O</i>(<i>W</i> log <i>n</i>) time using expected <i>O</i>((<i>d</i>+<i>W</i>)<i>n</i> log <i>n</i>) messages of size <i>O</i>(<i>W</i>) each. Furthermore, the algorithm has low <i>contention</i>: at any time there are only <i>O</i>(<i>d</i>) undelivered messages for any given recipient. A lower bound of Ω(<i>d</i> + log <i>n</i>) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-<i>d</i> weakly-connected graph of <i>n</i> nodes. We conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.
3103973
Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks
Mobile ad hoc networking has been an active research area for several years. How to stimulate cooperation among selfish mobile nodes, however, is not well addressed yet. In this paper, we propose Sprite, a simple, cheat-proof, credit-based system for stimulating cooperation among selfish nodes in mobile ad hoc networks. Our system provides incentive for mobile nodes to cooperate and report actions honestly. Compared with previous approaches, our system does not require any tamper-proof hardware at any node. Furthermore, we present a formal model of our system and prove its properties. Evaluations of a prototype implementation show that the overhead of our system is small. Simulations and analysis show that mobile nodes can cooperate and forward each other's messages, unless the resource of each node is extremely low.
8876890
Overlay mesh construction using interleaved spanning trees
In this paper we evaluate a method of using interleaved spanning trees to compose a resilient, high performance overlay mesh. Though spanning trees of arbitrary type could be used to construct an overlay mesh, we focus on a distributed algorithm that computes k minimum spanning trees on an arbitrary graph. The principal motivation behind this strategy is to provide applications with a k-redundant, high quality mesh suitable for demanding applications like A/V broadcast, video conferencing, data collection, multi-path routing, and file mirroring/transfer. We elaborate details of k-MST, pointing out advantages and potential problem points of the protocol, and then analyze its performance using a variety of metrics with simulation as well as a functional PlanetLab implementation.
16222163
Learning a Hidden Hypergraph
We consider the problem of learning a hypergraph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden hypergraph or not. We show that an r-uniform hypergraph with m edges and n vertices is learnable with O(2 4r m.poly(r,logn)) queries with high probability. The queries can be made in O(min(2 r r 2 log 2 n, r 3 log 3 n)) rounds. We also give an algorithm that learns a non-uniform hypergraph whose minimum edge size is r 1 and maximum edge size is r 2 using O(f 1 (r 1 ,r 2 ).m (r 2 -r 1 +2)/2 . poly(log n)) queries with high probability, and give a lower bound of Ω(f 2 (r 1 ,r 2 ).m (r 2 -r 1 +2)/2 for this class of hypergraphs, where fi and f 2 are functions depending only on r 1 and r 2 . The queries can also be made in O(min(2 r 2r 2 2 log 2 n, r 3 2 log 3 n)) rounds.
33317527
Learning Large-Alphabet and Analog Circuits with Value Injection Queries
We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced circuits, we develop the Distinguishing Paths Algorithm, that learns such a circuit using (ns)O(k) value injection queries and time polynomial in the number of queries. We describe a generalization of the algorithm to the class of circuits with shortcut width bounded by b that uses (ns)O(k+b) value injection queries. Both algorithms use value injection queries that fix only O(kd) wires, where d is the depth of the target circuit. We give a reduction showing that without such restrictions on the topology of the circuit, the learning problem may be computationally intractable when s = nΘ(1), even for circuits of depth O(log n). We then apply our large-alphabet learning algorithms to the problem of approximate learning of analog circuits whose gate functions satisfy a Lipschitz condition. Finally, we consider models in which behavioral equivalence queries are also available, and extend and improve the learning algorithms of [5] to handle general classes of gates functions that are polynomial time learnable from counterexamples.
5765721
Architecture of TsinghuAeolus
RoboCup Simulation Server provides a wonderful challenge for all the participants. This paper explains key technology implemented by Tsinghuaeolus RoboCup team played in RoboCup environment, including basic adversarial skills, which is developed by using Dynamic Programming in combination with heuristic search algorithm, and reactive strategy architecture. Tsinghuaeolus was the winner of RoboCup2001.
2698140
On fixed-parameter tractability and approximability of NP-hard optimization problems
Fixed-parameter tractability and approximability of NP-hard optimization problems are studied based on a model GC(s(n), Pi /sub k//sup L/). The main results are (1) a class of NP-hard optimization problems, including dominating-set and zero-one integer-programing, are fixed-parameter tractable if and only if GC(s(n), Pi /sub 2//sup L/) contained in P for some s(n) in omega (log n); (2) most approximable NP-hard optimization problems are fixed-parameter tractable. In particular, the class MAX NP is fixed-parameter tractable; (3) a class of optimization problems do not have fully polynomial time approximation scheme unless GC(s(n), Pi /sub k//sup L/) contained in P for some s(n) in omega (log n) and for some k>l; and (4) every fixed-parameter tractable optimization problem can be approximated in polynomial time to a non-trivial ratio.<<ETX>>
932171
On strong Menger-connectivity of star graphs
Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a graph of minimum vertex degree d. We say that G is strongly Menger-connected if for any copy Gf of G with at most d - 2 nodes removed, every pair of nodes u and v in Gf are connected by min{degf(u), degf(v)} node-disjoint paths in Gf, where degf(u) and degf(v) are the degrees of the nodes u and v in Gf, respectively. We show that the star graphs, which are a recently proposed attractive alternative to the widely used hypercubes as network models, are strongly Menger-connected. An algorithm of optimal running time is developed that constructs the maximum number of node-disjoint paths of nearly optimal length in star graphs with faults.
3146463
On Strong Menger-Connectivity of Star Graphs
Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a d-regular graph. We say that G is strongly Menger-connected if for any copy Gf of G with at most d - 2 nodes removed, every pair of nodes u and v in Gf are connected by min{deg f(u), deg f(v)} node-disjoint paths in Gf, where deg f(u) and deg f(v) are the degrees of the nodes u and v in Gf, respectively. We show that the star graphs, which are a recently proposed attractive alternative to the widely used hypercubes as network models, are strongly Menger-connected. An algorithm of optimal running time is developed that constructs the maximum number of node-disjoint paths of nearly optimal length in star graphs with faults.
26682479
Web-Based Collaborative Tools for Geospatial Data Exploration
Federal government agencies have collected large and highly complex federal statistical summaries and geo-reference data. Methods and tools for identifying patterns and uncovering multivariate relationships in the complex datasets have drawn attention in multiple fields. The approach we present here extends from and integrates perspectives from multiple fields, including exploratory data analysis (EDA), geovisualization, information visualization, and data mining. Important components of our research are supported by a NSF Digital Government grant (#99883451). Other support comes from a National Cancer Institute (NCI) contract. Our DG research is now being extended to develop comprehensive multivariate analysis methods and tools, through a grant from NCI (CA95949).
18252662
On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms
The constrained minimum vertex cover problem on bipartite graphs arises from the extensively studied fault coverage problem for reconfigurable arrays. In this paper, we develop a new algorithm for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation are nicely combined and extended. The algorithm is practically efficient with running time bounded by O(1.26k + kn), where k is the size of the constrained minimum vertex cover in the input graph. The algorithm is a significant improvement over the previous algorithms for the problem.