Catálogo de publicaciones - libros

In this paper, we consider the weighted online set - multicover problem. In this problem, we have an universe of elements, a family of subsets of with a positive real cost for every , and a “coverage factor” (positive integer) . A subset {, ,...} ⊆  of elements are presented online in an arbitrary order. When each element is presented, we are also told the collection of all (at least ) sets and their costs in which belongs and we need to select additional sets from if necessary such that our collection of selected sets contains sets that contain the element . The goal is to the of the selected sets. In this paper, we describe a new randomized algorithm for the online multicover problem based on the randomized winnowing approach of [11]. This algorithm generalizes and improves some earlier results in [1]. We also discuss lower bounds on competitive ratios for for general based on the approaches in [1].

A tree -spanner of a graph is a spanning tree of whose max-stretch is , i.e., the distance between any two vertices in is at most times their distance in . If has a tree -spanner but not a tree (–1)-spanner, then is said to have max-stretch of . In this paper, we study the Max-Stretch Reduction Problem: for an unweighted graph = (,), find a set of edges not in originally whose insertion into can decrease the max-stretch of . Our results are as follows: (i) For a ring graph, we give a linear-time algorithm which inserts edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is -hard to decide, for a given graph and its spanning tree of max-stretch , whether or not one-edge insertion can decrease the max-stretch to – 1. (iv) Finally, we show that the max-stretch of an arbitrary graph on vertices can be reduced to ′≥ 2 by inserting (/′) edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant.

We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented.

For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with faces of a surface with genus , our representation requires asymptotically an extra amount of 36( - 1)lg bits (which is negligible as long as  ≪ /lg ).

We present a space-efficient algorithm for reporting all intersections induced by a set of line segments in the place. Our algorithm is an in-place variant of Balaban’s algorithm and runs in time using (1) extra words of memory over and above the space used for the input to the algorithm.

Settling a ten years open question, we show that the NP-complete problem is deterministically solvable in ( · ) time, where  denotes the number of graph edges, denotes the size of the feedback vertex set searched for, and  is a constant. As a second result, we present a fixed-parameter algorithm for the NP-complete problem with runtime (2 · ).

We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops.

The associated clustering problem is as follows: Given points in , find a size- subset with minimum average pairwise distance. We present a natural approximation algorithm and show that it is a -approximation for 2D grids. In dimensions, the approximation guarantee is 2 - , which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension and report on experimental results.

Consider a directed rooted tree  = (,) representing a collection of web pages connected via a set of links all reachable from a source home page, represented by the root of . Each web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendents, we are interested in minimizing the expected number of steps needed to visit pages from the home page. We give the first linear time algorithm for assigning hotlinks so that the number of steps to accede to a page from the root of the tree reaches the entropy bound, i.e. is at most where  = ∑ . The best previously known algorithm for this task runs in time (). We also give the first efficient data structure for maintaining hotlinks when nodes are added, deleted or their weights modified, in amortized time per update. The data structure can be made adaptative, i.e. reaches the entropy bound in the amortized sense without knowing the weights in advance.

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree () problem: Given a set of points in the plane, find a spanning tree of of minimum “area,” where the area of a spanning tree is the area of the union of the –1 disks whose diameters are the edges in . We prove that the Euclidean minimum spanning tree of is a constant-factor approximation for . We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment () problem, for the Minimum-Area Connected Disk Graph () problem, and for the Minimum-Area Tour () problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.

This paper presents a general family of 3D hinged dissections for , i.e., connected 3D solids formed by joining several rigid copies of the same polyhedron along identical faces. (Such joinings are possible only for reflectionally symmetric faces.) Each hinged dissection consists of a linear number of solid polyhedral pieces hinged along their edges to form a flexible closed chain (cycle). For each base polyhedron and each positive integer , a single hinged dissection has folded configurations corresponding to all possible polypolyhedra formed by joining copies of the polyhedron . In particular, these results settle the open problem posed in [7] about the special case of polycubes (where is a cube) and extend analogous results from 2D [7].Along the way, we present hinged dissections for polyplatonics (where is a platonic solid) that are particularly efficient: among a type of hinged dissection, they use the fewest possible pieces.

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc. e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.

When a coloring of a tree is not convex, it is desirable to know ”how far” it is from a convex one, and what are the convex colorings which are ”closest” to it. In this paper we study a natural definition of this distance – the , which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a path, and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the model and the model. Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in linear time for any fixed number of colors. Next we improve these algorithms for the uniform model to run in linear time for any fixed number of colors. Finally, we generalize the above result to hold for trees of unbounded degree.