Catálogo de publicaciones - libros

Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound for this problem.

The past few years have witnessed different scheduling algorithms for a processor that can manage its energy usage by scaling dynamically its speed. In this paper we attempt to extend such work to the two-processor setting. Specifically, we focus on deadline scheduling and study online algorithms for two processors with an objective of maximizing the throughput, while using the smallest possible energy. The motivation comes from the fact that dual-core processors are getting common nowadays. Our first result is a new analysis of the energy usage of the speed function OA [15,4,8] with respect to the optimal two-processor schedule. This immediately implies a trivial two-processor algorithm that is 16-competitive for throughput and (1)-competitive for energy. A more interesting result is a new online strategy for selecting jobs for the two processors. Together with OA, it improves the competitive ratio for throughput from 16 to 3, while increasing that for energy by a factor of 2. Note that even if the energy usage is not a concern, no algorithm can be better than 2-competitive with respect to throughput.

In this paper we give a finer separation of several known paging algorithms. This is accomplished using a new technique that we call relative interval analysis. The technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size rather than in the worst case alone. Using this technique we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that lookahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.

We present improved and simplified -efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a low-density subdivision with edges in ’s into a compressed linear quadtree such that one can:

For the special case where the subdivision is a fat triangulation, we show how to obtain the same bounds with an ordinary (uncompressed) quadtree, and we show how to make the structure fully dynamic using (log) ’s per update. Our algorithms and data structures improve on the previous best known bounds for general subdivisions both in the number of ’s and storage usage, they are significantly simpler, and several of our algorithms are cache-oblivious.

We solve several fundamental geometric problems under a new streaming model recently proposed by Ruhl et al. [2,12]. In this model, in one pass the input stream can be scanned to generate an output stream or be sorted based on a user-defined comparator; all intermediate streams must be of size (). We obtain the following geometric results for any fixed constant > 0: We also consider a weaker model, where we do not have the sorting primitive but are allowed to choose a scan direction for every scan pass. Here we can construct a 2D convex hull from an -ordered point set in (1) passes with () extra space.

In this paper we present external memory data structures for orthogonal range reporting queries on a grid. Our data structure for two-dimensional orthogonal range reporting queries uses ((/)log) blocks of space of size and supports queries in optimal (log log + /) time, where is the size of universe, is the number of elements in the data structure, and is the size of the answer. Our data structure for three-sided range reporting queries that uses (/) blocks of space and supports queries in (log log + /) time. In the case of three-sided range reporting on a ×ℕ grid, we describe a space data structure with (/) query time, a data structure with query time, and a (/) space data structure with query time for any constant .

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the , stores a set of points in ℝ and can report all points inside a query range by accessing (log +  + /) disk blocks, where is the disk block size, = 1 −  for convex queries and = −  otherwise, and is the number of points lying within a distance of ·diam() to the query range . Our second structure, the , is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures also support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.

We study the explicit deterministic treasure hunt problem in an -vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in [9] [SODA’07]. It is the variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. We obtain an -time solution for this problem, which significantly improves the currently best known result of running time () in [9], where is a fixed constant from the construction of an universal exploration sequence in [8,9], is a constant integer and  ≫ 1. The treasure hunt problem motivates the study of strongly universal exploration sequences. We give a better explicit construction of strongly universal exploration sequences than the one in [9].

Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for for fixed values of the grooming factor , answering affirmatively the conjecture of Chow and Lin (). More precisely, we prove that for fixed  ≥ 1 and for fixed  ≥ 2 are APX-complete. That is, they do not accept a PTAS unless P= NP. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length 2 + 1 in a graph of girth 2 + 1) is APX-complete.

On the other hand, we provide a polynomial-time approximation algorithm for and , based on a greedy cover algorithm, with an approximation ratio independent of . Namely, the approximation guarantee is for any  ≥ 1, being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph.

Social networks support efficient decentralized search: people can collectively construct short paths to a specified target in the network. —where the probability that person  befriends person is inversely proportional to the number of people who are closer to than is—is an empirically validated model of acquaintanceship that provably results in efficient decentralized search via greedy routing, even in networks with variable population densities. In this paper, we introduce , a variant of greedy that avoids taking large jumps unless they make substantial progress towards the target. Our main result is that cautious-greedy routing finds a path of short expected length from an arbitrary source to a randomly chosen target, independent of the population densities. To quantify the expected length of the path, we define the of a metric space, a new quantity that intuitively measures the “width” of directions that leave a point in the space. Our main result is that cautious-greedy routing finds a path of expected length (log) in -person networks that have aspect ratio polynomial in , bounded doubling dimension, and bounded depth of field. Specifically, in -dimensional grids under Manhattan distance with arbitrary population densities, the (log) expected path length that we achieve with the cautious-greedy algorithm improves the best previous bound of (log) with greedy routing.