8789607
Networks preserving evolutionary equilibria and the power of randomization
We study a natural extension of classical evolutionary game theory to a setting in which pairwise interactions are restricted to the edges of an undirected graph or network. We generalize the definition of an evolutionary stable strategy (ESS), and show a pair of complementary results that exhibit the power of randomization in our setting: subject to degree or edge density conditions, the classical ESS of any game are preserved when the graph is chosen randomly and the mutation set is chosen adversarially, or when the graph is chosen adversarially and the mutation set is chosen randomly. We examine natural strengthenings of our generalized ESS definition, and show that similarly strong resultsnare not possible for them.
1819914
Economic Properties of Social Networks
We examine the marriage of recent probabilistic generative models for social networks with classical frameworks from mathematical economics. We are particularly interested in how the statistical structure of such networks influences global economic quantities such as price variation. Our findings are a mixture of formal analysis, simulation, and experiments on an international trade data set from the United Nations.
11153751
Graph distances in the streaming model: the value of space
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order. The main computational restriction of the model is that we have limited space and therefore cannot store all the streamed data; we are forced to make space-efficient summaries of the data as we go along. For a graph of <i>n</i> vertices and <i>m</i> edges, we show that testing many graph properties, including connectivity (<i>ergo</i> any reasonable decision problem about distances) and bipartiteness, requires Ω(<i>n</i>) bits of space. Given this, we then investigate how the power of the model increases as we relax our space restriction. Our main result is an efficient randomized algorithm that constructs a (2<i>t</i> + 1)-spanner in one pass. With high probability, it uses <i>O(t .n</i><sup>1+1/<i>t</i></sup> log<sup>2</sup><i>n</i>) bits of space and processes each edge in the stream in <i>O(t</i><sup>2</sup>·<i>n</i><sup>1/<i>t</i></sup> log <i>n</i>) time. We find approximations to diameter and girth via the constructed spanner. For <i>t</i> = Ω(log <i>n</i>/log log <i>n</i>), the space requirement of the algorithm is <i>O(n</i> .polylog <i>n</i>), and the per-edge processing time is <i>O</i>(polylog <i>n</i>). We also show a corresponding lower bound of <i>t</i> for the approximation ratio achievable when the space restriction is <i>O(t.n</i><sup>1+1/<i>t</i></sup> log<sup>2</sup><i>n</i>).We then consider the scenario in which we are allowed multiple passes over the input stream. Here, we investigate whether allowing these extra passes will compensate for a given space restriction. We show that finding vertices at distance <i>d</i> from a particular vertex will always take <i>d</i> passes, for all <i>d</i> ∈ {1,...,<i>t</i>/2}, when the space restriction is <i>o</i>(<i>n</i><sup>1+1/<i>t</i></sup>). For girth, we show the existence of a direct trade-off between space and passes in the form of a lower bound on the product of the space requirement and number of passes. Finally, we conclude with two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by at most a log factor.
7086886
On graph problems in a semi-streaming model
We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G = (V, E), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O(n ċ polylog n), where n = |V|. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithmic improvement for the bipartite case. We also exhibit log n/log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω(log(1-e) n) lower bounds.
206997432
Range Counting over Multidimensional Data Streams
AbstractWe consider the problem of approximate range counting over a stream of d-dimensional points. In the data stream model the algorithm makes a single scan of the data, which is presented in an arbitrary order, and computes a compact summary data
structure. The summary, whose size depends on the approximation parameter ε, can be used to count the number of points inside a query range within additive error εn, where n is the size of the stream seen so far. We present several results, deterministic and randomized, for both rectangle and halfspace ranges.
2604122
Stabbing triangulations by lines in 3D
Let S be a set Stabbing Triangulations by Lines in 3D* Pankaj K. Agarwalt Boris Aronov$ Subllasll SuriS of (possibly degenerate) triangles in iR3 whose interiors are-disjoint. A-triangulation ~f !R3 with respect to S, denoted by T(s), is a simplicial complex in which each face of ‘T(S) is either disjoint from S or contained in a higher dimensional face of S. The line stabbing number of T(S) is the maximum number of tetrahedral of T(S) intersected by a segment that does not intersect any triangle of S. We investigate the line stabbing number of triangulations in several cases— when S is a set of points, when the triangles of S form the boundary of a convex or a nonconvex polyhedron, or when the triangles of S form the boundaries of k disjoint convex polyhedra. We prove almost tight worst-case upper and lower bounds on line stabbing numbers for these cases. We also estimate the number of tetrahedral necessary to guarantee low stabbing number. *The work by the first author was supported by National Science Foundation Grant Grant CC R-93–Ol 259, an NYI award, and by matching funds from Xerox Corp. The work by the second author was supported by National Science Foundation Grant CCR92-11541. t Department of Computer Science, Box 90129, Duke University, Durham, NC 27708-0129. t Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NY 11201. sDepartment of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO 63130. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association of Computing Machinery.To copy otherwise, or to republish, requires a fee and/or specific permission. 1Ith Computational Geometry, Vancouver, B.C. Canada @ 1995 ACM 0-89791 -724 -3/95/0006 ...$3.50
1493868
An Optimal Algorithm for Euclidean Shortest Paths in the Plane
We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources.
28274388
Query-Sensitive Ray Shooting
Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by wallking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(nlogn), where n is the total number of vertices in all the obstacles.