Algorithms and Data Structures

Quantum entanglement, perhaps the most non-classical manifestation of quantum information theory, cannot be used to transmit information between remote parties. Yet, it can be used to reducethe amount of communication required to process a variety of distributedcomputational tasks. We speak of pseudo-telepathy when quantum entanglementserves to eliminate the classical need to communicate. In earlier examples of pseudo-telepathy, classical protocols could succeedwith high probability unless the inputs were very large. Here we present a simple multi-party distributed problem for which the inputsand outputsconsist of a single bit per player, and we present a perfectquantum protocolfor it. We prove that no classical protocol can succeedwith a probability that differs from 1/2 by more than a fraction that is exponentially small in the number of players. This could be used to circumvent the detection loophole in experimental tests of nonlocality.

In geometric data processing, structures that partition the geometric input, as well as connectivity structures for geometric objects, play an important role. A versatile tool in this context are triangular meshes, often called triangulations; see e.g., the survey articles [6, 12, 5]. A triangulation of a finite set S of points in the plane is a maximal planar straight-line graph that uses all and only the points in S as its vertices. Each face in a triangulation is a triangle spanned by S. In the last few years, a relaxation of triangulations, called pseudo-triangulations (or geodesic triangulations), has received considerable attention. Here, faces bounded by three concave chains, rather than by three line segments, are allowed. The scope of applications of pseudo-triangulations as a geometric data stucture ranges from ray shooting [10, 14] and visibility [25, 26] to kinetic collision detection [1, 21, 22], rigidity [32, 29, 15], and guarding [31]. Still, only very recently, results on the combinatorial properties of pseudo-triangulations have been obtained. These include bounds on the minimal vertex and face degree [20] and on the number of possible pseudo-triangulations [27, 3]. The usefulness of (pseudo-)triangulations partially stems from the fact that these structures can be modified by constant-size combinatorial changes, commonly called flip operations. Flip operations allow for an adaption to local requirements, or even for generating globally optimal structures [6, 12]. A classical result states that any two triangulations of a given planar point set can be made to coincide by applying a quadratic number of edge flips; see e.g. [16, 19]. A similar result has been proved recently for the class of minimum pseudo-triangulations [8, 29].

Geometric shapes are identified with their features. For computational purposes a concrete mathematical definition of features is required. In this paper we use a topological approach, namely dynamical systems, to define features of shapes. To exploit this definition algorithmically we assume that a point sample of the shape is given as input from which features of the shape have to be approximated. We translate our definition of features to the discrete domain while mimicking the set-up developed for the continuous shapes. Experimental results show that our algorithms segment shapes in two and three dimensions into so-called features quite effectively. Further, we develop a shape matching algorithm that takes advantage of our robust feature segmentation step.

Phylogenetic reconstruction from gene-rearrangement data has seen increased attention over the last five years. Existing methods are limited computationally and by the assumption (highly unrealistic in practice) that all genomes have the same gene content. We have recently shown that we can scale our reconstruction tool, GRAPPA, to instances with up to a thousand genomes with no loss of accuracy and at minimal computational cost. Computing genomic distances between two genomes with unequal gene contents has seen much progress recently, but that progress has not yet been reflected in phylogenetic reconstruction methods. In this paper, we present extensions to our GRAPPA approach that can handle limited numbers of duplications (one of the main requirements for analyzing genomic data from organelles) and a few deletions. Although GRAPPA is based on exhaustive search, we show that, in practice, our bounding functions suffice to prune away almost all of the search space (our pruning rates never fall below 99.995%), resulting in high accuracy and fast running times. The range of values within which we have tested our approach encompasses mitochondria and chloroplast organellar genomes, whose phylogenetic analysis is providing new insights on evolution.

We present algorithms that reduce the time and space needed to solve problems of finding all motifs common to a set of sequences. In particular, we give algorithms that (1) require time and space linear in the size of the input, (2) succinctly encode the output so that the time and space requirements depend on the number of motifs, not directly on motif length, and (3) efficiently parallelize the enumeration.

The lazy bureaucrat scheduling is a new class of scheduling problems that was introduced in [1]. In these problems, there is one employee (or more) who should perform the assigned jobs. The objective of the employee is to minimize the amount of work he performs and to be as inefficient as possible. He is subject to a constraint, however, that he should be busy when there is some work to do.In this paper, we focus on the cases of this problem where all jobs have the same common deadline. We show that with this constraint, the problem is still NP-hard, and prove some hardness results. We then present a tight 2-approximation algorithm for this problem under one of the defined objective functions. Moreover, we prove that this problem is weakly NP-hard under all objective functions, and present a pseudo-polynomial time algorithm for its general case.

Grid computing systems pool together the resources of many workstations to create a virtual computing reservoir. Users can “draw” resources using a pay-as-you-go model, commonly used for utilities (electricity and water). We model such a system as a capacitated graph, and study a basic allocation problem: given a set of jobs, each demanding computing and bandwidth resources and yielding a profit, determine which feasible subset of jobs yields the maximum total profit.

We consider the problem of minimum lateness/tardiness scheduling with rejection for which the objective function is the sum of the maximum lateness/tardiness of the scheduled jobs and the total rejection penalty (sum of rejection costs) of the rejected jobs. If rejection is not considered, the problems are solvable in polynomial time using the Earliest Due Date (EDD) rule. We show that adding the option of rejection makes the problems $\mathcal{NP}$-complete. We give pseudo-polynomial time algorithms, based on dynamic programming, for these problems. We also develop a fully polynomial time approximation scheme (FPTAS) for minimum tardiness scheduling with rejection using a geometric rounding technique on the total rejection penalty.Observe that the usual notion of an approximation algorithm (guaranteed factor bound relative to optimal objective function value) is inappropriate when the optimal objective function value could be negative, as is the case with minimum lateness scheduling with rejection. An alternative notion of approximation, called ε-optimization approximation [7], is suitable for designing approximation algorithms for such problems. We give a polynomial time ε-optimization approximation scheme (PTEOS) for minimum lateness scheduling with rejection and a fully polynomial time ε-optimization approximation scheme (FPTEOS) for a modified problem where the total rejection penalty is the product (and not the sum) of the rejection costs of the rejected jobs.

Given a set of n objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing efficient indexing structures such that the following type of queries can be handled efficiently: given d value ranges and a time interval, report or count all the objects whose attributes fall within the corresponding d value ranges at each time instance lying in the specified time interval. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of O(log n log m + f) for one-sided queries when d=1, where f is the output size. We also show that the most general problem can be solved with polylogarithmic query time using nonlinear space data structures.

A new priority queue structure is introduced, for which the amortized time to insert a new element is O(1) while that for the minimum-extraction is $O({\rm log} \bar{K})$. $\bar{K}$ is the average, taken over all the deleted elements x, of the number of elements that are inserted during the lifespan of x and are still in the heap when x is removed. Several applications of our structure are mentioned.

We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes O(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting keys take O(log n) time. We show that these bounds can be simultaneously achieved in the worst case for searching and updating by suitably maintaining a permutation of the n keys in the array. The resulting data structure is called implicit as it uses just O(1) extra memory cells beside the n cells for the array. The data structure is also cache-oblivious, attaining O(log_Bn) block transfers in the worst case for any (unknown) value of the block size B, without wasting any single cell of memory at any level of the memory hierarchy.

This paper studies a variety of problems involving certain types of extreme configurations in arrangements of (x-monotone) pseudo-lines. For example, we obtain a very simple proof of the bound O(nk1/3) on the maximum complexity of the k-th level in an arrangement of n pseudo-lines, which becomes even simpler in the case of lines. We thus simplify considerably the previous proof by Tamaki and Tokuyama (and also simplify Dey’s proof for lines).We also consider diamonds and anti-diamonds in (simple) pseudo-line arrangements, where a diamond (resp., an anti-diamond) is a pair u,v of vertices, so that u lies in the double wedge of v and vice versa (resp., neither u nor v lies in the other double wedge). We show that the maximum size of a diamond-free set of vertices in an arrangement of n pseudo-lines is 3n—6, by showing that the induced graph (where each vertex of the arrangement is regarded as an edge connecting the two incident curves) is planar, simplifying considerably a previous proof of the same fact by Tamaki and Tokuyama. Similarly, we show that the maximum size of an anti-diamond-free set of vertices in an arrangement of n pseudo-lines is 2n—2. We also obtain several additional results, which are listed in the introduction.In some of our results, we use a recent duality transform between points and pseudo-lines due to Agarwal and Sharir, which extends an earlier transform by Goodman (that applied only in the projective plane). We show that this transform maps a set of vertices in a pseudo-line arrangement to a topological graph whose edges are drawn as x-monotone arcs that connect pairs of the dual points, and form a set of extendible pseudo-segments (they are pieces of curves that form a pseudo-line arrangement in the dual plane). This allows us (a) to ‘import’ known results on this kind of topological graphs to the context of pseudo-lines; (b) to extend techniques that have been originally applied only for geometric graphs (whose edges are drawn as straight segments), thereby obtaining new results for pseudo-line arrangements, or for the above-class of x-monotone topological graphs; and (c) to derive new techniques, facilitated by the passage to the dual setting, that apply in the more general pseudo-line context, and extend and simplify considerably the earlier proofs. This paper contains examples of all three kinds of results.

Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given absolute precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable relative error ε> 0 in time $\mathcal{O}(\frac{1}{\epsilon}N \cdot {\rm polylog}N)$.

We consider the one-round Voronoi game, where player one (“White”, called “Wilma”) places a set of n points in a rectangular area of aspect ratio ρ ≤ 1, followed by the second player (“Black”, called “Barney”), who places the same number of points. Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area. This problem has been studied by Cheong et al. who showed that for large enough n and ρ = 1, Barney has a strategy that guarantees a fraction of 1/2+α, for some small fixed α.We resolve a number of open problems raised by that paper. In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n ≥ 3 and $\rho > \sqrt{2}/n$, and for n=2 and $\rho > \sqrt{3}/2$. Wilma wins in all remaining cases, i.e., for n ≥ 3 and $\rho \leq \sqrt{2}/n$, for n=2 and $\rho \leq \sqrt{3}/2$, and for n=1. We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.

All previous work on integrated prefetching/caching assumes that memory reference strings consist of read requests only. In this paper we present the first study of integrated prefetching/caching with both read and write requests. For single disk systems we analyze popular algorithms such as Conservative and Aggressive and give tight bounds on their approximation ratios. We also develop a new algorithm that performs better than Conservative and Aggressive. For parallel disk systems we present a general technique to construct feasible schedules. The technique achieves a load balancing among the disks. Finally we show that it is NP-complete to decide if an input can be served with f fetch and w write operations, even in the single disk setting.

When reservations are made to for instance a train, it is an on-line problem to accept or reject, i.e., decide if a person can be fitted in given all earlier reservations. However, determining a seating arrangement, implying that it is safe to accept, is an off-line problem with the earlier reservations and the current one as input. We develop optimal algorithms to handle problems of this nature.

A vast majority of communications in a network occurs between pairs of nodes, each such interaction is termed a call. The job of a call control algorithm is to decide which of a set of calls to accept in the network so as to maximize the number of accepted calls or the profit associated with the accepted calls. When a call is accepted it uses up some network resources, like bandwidth, along the path through which it is routed. The call control algorithm needs to make intelligent trade-offs between resource constraints and profits. We investigate two variants of call control problems on ring networks; in the first, the algorithm is allowed to determine the route connecting the end nodes of a call, while in the second, the route is specified as part of the input. For the first variant, we show an efficient algorithm that achieves the objective of routing and maximizing the number of accepted calls within an additive constant of at most 3 to an optimal algorithm. For the fixed path variant, we derive a 2-approximation for maximizing the profits (which could be arbitrary) of accepted calls. For several important special cases we show polynomial time optimal algorithms.

Mobility is increasing in a way that calls for systematic traffic planning in a broad context. In Europe the railways are requested to play a central role in this development. Future developments and improvements of European railways will have an impact on people’s lives and therefore on society in general. The problems arising in this context are large and highly complex. Here are many interesting and challenging algorithmic problems waiting to be studied. Research topics include the network design, line planning, time table generation, crew scheduling, rolling stock rostering, shunting, time table information and delay management.In this talk we present models and algorithmic methods for several of these problems. We will discuss the interplay between algorithmic aspects and practical issues like availability and quality of data. The focus will be on two topics from network design and time table information respectively where we have ongoing cooperation with railway companies. As an example from network design, we will consider a scenario where the effects of introducing new train stops in the existing railway network is studied. For time table information whose algorithmic core problem is the computation of shortest paths we discuss new algorithmic issues arising from the huge size of the underlying data.

We consider the problem of finding a shortest rectilinear Steiner tree for a given set of points in the plane in the presence of rectilinear obstacles. The Steiner tree is allowed to run over obstacles; however, if we intersect the Steiner tree with some obstacle, then no connected component of the induced subtree must be longer than a given fixed length L. This kind of length restriction is motivated by its application in VLSI design where a large Steiner tree requires the insertion of buffers (or inverters) which must not be placed on top of obstacles.We show that the length-restricted Steiner tree problem can be approximated with a performance guarantee of 2 in O(n logn) time, where n denotes the size of the associated Hanan grid. Optimal length-restricted Steiner trees can be characterized to have a special structure. In particular, we prove that a certain graph, which is a variant of the Hanan grid, always contains an optimal solution. Based on this structural result, we can improve the performance guarantee of approximation algorithms for the special case that all obstacles are of rectangular shape or of constant complexity, i.e. they are represented by at most a constant number of edges. For such a scenario, we give a $\frac{5}{4}\alpha$-approximation and a $\frac{2k}{2k-1}\alpha$-approximation for any integral k ≥ 4, where α denotes the performance guarantee for the ordinary Steiner tree problem in graphs.

In this paper, we introduce a new data structure, the multi-way space partitioning (MSP) tree similar in nature to the standard binary space partitioning (BSP) tree. Unlike the super-linear space requirement for BSP trees, we show that for any set of disjoint line segments in the plane there exists a linear-size MSP tree completely partitioning the set. Since our structure is a deviation from the standard BSP tree construction, we also describe an application of our algorithm. We prove that the well-known Painter’s algorithm can be adapted quite easily to use our structure to run in O(n) time. More importantly, the constant factor behind our tree size is extremely small, having size less than 4n.

Watermarking is a frequently used tool for digital rights management. An example of this is using watermarks to place ownership information into an object. There are many instances where placing multiple watermarks into the same object is desired. One mechanism that has been proposed for doing this is segmenting the data into a grid and placing watermarks into different regions of the grid. This is particularly suited for images and geographic information systems (GIS) databases as they already consist of a fine granularity grid (of pixels, geographic regions, etc.); a grid cell for watermarking is an aggregation of the original fine granularity cells. An attacker may be interested in only a subset of the watermarked data, and it is crucial that the watermarks survive in the subset selected by the attacker. In the kind of data mentioned above (images, GIS, etc.) such an attack typically consists of cropping, e.g. selecting a geographic region between two latitudes and longitudes (in the GIS case) or a rectangular region of pixels (in an image). The contribution of this paper is a set of schemes and their analysis for multiple watermark placement that maximizes resilience to the above mentioned cropping attack. This involves the definition of various performance metrics and their use in evaluating and comparing various placement schemes.

We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. In particular, given a mapping, we show how to embed two paths on an n ×n grid, and two caterpillar graphs on a 3n ×3n grid. We show that it is not always possible to simultaneously embed three paths. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) ×O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n2) ×O(n2) grid.

In smoothed analysis, one measures the complexity of algorithms assuming that their inputs are subject to small amounts of random noise. In an earlier work (Spielman and Teng, 2001), we introduced this analysis to explain the good practical behavior of the simplex algorithm. In this paper, we provide further motivation for the smoothed analysis of algorithms, and develop models of noise suitable for analyzing the behavior of discrete algorithms. We then consider the smoothed complexities of testing some simple graph properties in these models.

Hotlink assignment concerns the addition of shortcut links to information structures based on linked nodes such as the web. Each node in the structure is associated with a weight representing the frequency that node is accessed by users. To access a node, the user must follow the path leading to it from the root. Introducing additional edges (hotlinks) to the structure may reduce its access cost, taken to be the expected number of steps needed to reach a node from the root. The hotlink assignment problem is to find a set of hotlinks achieving the greatest improvement in the access cost. This paper introduces an approximation algorithm for this problem with approximation ratio 2.

We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and information traveling through the network. We present an efficient linear-time algorithm which draws edges and vertices of varying 2-dimensional areas to represent the amount of information flowing through them. The algorithm avoids all occlusions of nodes and edges, while still drawing the graph on a compact integer grid.

We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices. We refer to this problem as the semi-matching problem; it is a relaxation of the known bipartite matching problem. We present a way to evaluate the quality of a given semi-matching and show that, under this measure, an optimal semi-matching balances the load on the right hand vertices with respect to any L _p -norm. In particular, when modeling a job assignment system, an optimal semi-matching achieves the minimal makespan and the minimal flow time for the system.The problem of finding optimal semi-matchings is a special case of certain scheduling problems for which known solutions exist. However, these known solutions are based on general network optimization algorithms, and are not the most efficient way to solve the optimal semi-matching problem. To compute optimal semi-matchings efficiently, we present and analyze two new algorithms. The first algorithm generalizes the Hungarian method for computing maximum bipartite matchings, while the second, more efficient algorithm is based on a new notion of cost-reducing paths. Our experimental results demonstrate that the second algorithm is vastly superior to using known network optimization algorithms to solve the optimal semi-matching problem. Furthermore, this same algorithm can also be used to find maximum bipartite matchings and is shown to be roughly as efficient as the best known algorithms for this goal.

We show how to find a Hamiltonian cycle in a graph of degree at most three with n vertices, in time $\mathcal{O}(2^{n/3}) \approx {\rm 1.25992}^n$ and linear space. Our algorithm can find the minimum weight Hamiltonian cycle (traveling salesman problem), in the same time bound, and count the number of Hamiltonian cycles in time $\mathcal{O}(2^{3n/8}n^{\mathcal{O}(1)}) \approx {\rm 1.29684}^n$. We also solve the traveling salesman problem in graphs of degree at most four, by a randomized (Monte Carlo) algorithm with runtime $\mathcal{O}((27/4)^{n/3}) \approx {\rm 1.88988}^n$. Our algorithms allow the input to specify a set of forced edges which must be part of any generated cycle.

Unsigned circular permutations are used to represent tours in the traveling salesman problem as well as the arrangement of gene loci in circular chromosomes. The minimum number of segment reversals required to transform one circular permutation into another gives some measure of distance between them which is useful when studying the 2-opt local search landscape for the traveling salesman problem, and, when determining the phylogeny of a group of related organisms. Computing this distance is equivalent to sorting by (a minimum number of) reversals. In this paper we show that sorting circular permutations by reversals can be reduced to the same problem for linear reversals, and that it is NP-hard. These results suggest that for most practical purposes any computational tools available for reversal sort of linear permutations will be sufficiently accurate.These results entail the development of the algebraic machinery for dealing rigorously with circular permutations.

We consider the problem of computing the product of two n ×n Boolean matrices A and B.For two 0-1 strings s=s₁s₂....s _m and u=u₁u₂...u _m , an extended Hamming distance, eh(s,u), between the strings, is defined by a recursive equation eh(s,u) = eh(s _l + 1...s _m , u _l + 1...u _m ) + (s₁ + u₁ mod 2) where l is the maximum number, s.t., s _j =s₁ and u _j =u₁ for j=1,...,l. For any n ×n Boolean matrix C, let G _C be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning tree of G _C . We show that the product of A and B as well as the so called witnesses of the product can be computed in time Õ(n(n + 1 min{MWT(A), MWT(Bt)})).Since the extended Hamming distance between two strings never exceeds the standard Hamming distance between them, our result subsumes an earlier similar result on the Boolean matrix product in terms of the Hamming distance due to Björklund and Lingas [4]. We also observe that min$\{MWT(A), MWT(B^t)\} = O(min\{r_A, r_B\})$ where r _A and r _B reflect the minimum number of rectangles required to cover 1s in A and B, respectively. Hence, our result also generalizes the recent upper bound on the Boolean matrix product in terms of r _A and r _B , due to Lingas [12].

In this paper, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem, where the text update operation is changing the symbol value of a text location. Given a text of length n and a pattern of length m, our algorithm preprocesses the text in time O(nlog logm), and the pattern in time $O(m\sqrt{log m})$. The extra space used is $O(n + m\sqrt{log m})$. Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in O(log log m) time.

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision.Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. W e also present efficient algorithms for real scaled matching. The running time of our algorithm is as follows. If T is a two-dimensional n ×n text array and P is a m ×m pattern array, we find in T all occurrences of P scaled to any real value in time O(nm3 + n2m log m).

In this paper we study proximity structures like Delauney triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define several restricted Voronoi diagrams, restricted Delaunay triangulations, relative neighborhood graphs, Gabriel graphs and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks.

We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudo-triangulation zigzag path allows us to use divide-and-conquer type of approaches for suitable (i.e., decomposable) problems on pseudo-triangulations. For this we provide an algorithm that enumerates all pseudo-triangulation zigzag paths (of all pseudo-triangulations of a given point set with respect to a given line) in O(n2) time per path and O(n2) space, where n is the number of points. We illustrate applications of our scheme which include a novel algorithm to count the number of pseudo-triangulations of a point set.

It was shown recently that the segment endpoint visibility graph Vis(S) of any set S of n disjoint line segments in the plane admits an alternating path of length Θ(logn), and this bound is best possible apart from a constant factor. This paper focuses on the variant of the problem where S is a set of n disjoint axis-parallel line segments. We show that the length of a longest alternating path in the worst case is $\Theta(\sqrt{n})$. We also present an O(n2.5) time algorithm to find an alternating path of length $\Omega(\sqrt{n})$. Finally, we consider sets of axis-parallel segments where the extensions of no two segments meet in the free space $\mathbb{E}^2 \setminus \cup S$, and show that in that case all the segments can be included in a common alternating path.

The Quality of Service Steiner Tree Problem is a generalization of the Steiner problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the non-zero rate nodes is l ·r _e , where r _e is the maximum rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.211 for the case of unbounded number of rates. We give better approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for unbounded number of rates are reduced to 2.414 and 4.311, respectively.

A set of rectangles $\mathcal{S}$ is said to be grid packed if there exists a rectangular grid (not necessarily regular) such that every rectangle lies in the grid and there is at most one rectangle of $\mathcal{S}$ in each cell. The area of a grid packing is the area of a minimal bounding box that contains all the rectangles in the grid packing. We present an approximation algorithm that given a set $\mathcal{S}$ of rectangles and a real constant ε> 0 produces a grid packing of $\mathcal{S}$ whose area is at most (1 + ε) times larger than an optimal packing in polynomial time. If ε is chosen large enough the running time of the algorithm will be linear. We also study several interesting variants, for example the smallest area grid packing containing at least k ≤ n rectangles, and given a region $\mathcal{A}$ grid pack as many rectangles as possible within $\mathcal{A}$. Apart from the approximation algorithms we present several hardness results.

The design of heuristics for NP-hard problems is perhaps the most active area of research in the theory of combinatorial algorithms. However, practitioners more often resort to local-improvement heuristics such as gradient-descent search, simulated annealing, tabu search, or genetic algorithms. Properly implemented, local-improvement heuristics can lead to short, efficient programs that yield reasonable solutions. Designers of efficient local-improvement heuristics must make several crucial decisions, including the choice of neighborhood and heuristic for the problem at hand. We are interested in developing a general methodology for predicting the quality of local-neighborhood operators and heuristics, given a time budget and a solution evaluation function.

We study the Hausdorff Voronoi diagram of point clusters in the plane and derive a tight combinatorial bound on its structural complexity. We present a plane sweep algorithm for the construction of this diagram improving upon previous results. Motivation for the investigation of this type of Voronoi diagram comes from the problem of computing the critical area of a VLSI Layout, a measure reflecting the sensitivity of the design to spot defects during manufacturing.

Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes from R (respectively, B). This rule implicitly partitions space into a red set and a blue set that are separated by a red-blue decision boundary. In this paper we develop output-sensitive algorithms for computing this decision boundary for point sets on the line and in ℝ2. Both algorithms run in time O(n log k), where k is the number of points that contribute to the decision boundary. This running time is the best possible when parameterizing with respect to n and k.

In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of that color intersecting the query range. Such an object, however, could be an ‘outlier’ in its color class. Therefore we consider a variant of this problem where one has to report only those colors such that at least a fraction τ of the objects of that color intersects the query range, for some parameter τ. Our main results are on an approximate version of this problem, where we are also allowed to report those colors for which a fraction (1 - ε)τ intersects the query range, for some fixed ε> 0. We present efficient data structures for such queries with orthogonal query ranges in sets of colored points, and for point stabbing queries in sets of colored rectangles.

To determine if a graph has a spanning tree with few leaves is NP-hard. In this paper we study the parametric dual of this problem, k-Internal Spanning Tree (Does G have a spanning tree with at least k internal vertices?). We give an algorithm running in time O(24klogk ·k7/2 + k2 ·n2). We also give a 2-approximation algorithm for the problem.However, the main contribution of this paper is that we show the following remarkable structural bindings between k-Internal Spanning Tree and k-Vertex Cover: No for k-Vertex Cover implies Yes for k-Internal Spanning Tree.Yes for k-Vertex Cover implies No for (2k+1)-Internal Spanning Tree.We give a polynomial-time algorithm that produces either a vertex cover of size kor a spanning tree with at least k internal vertices. We show how to use this inherent vertex cover structure to design algorithms for FPT problems, here illustrated mainly by k-Internal Spanning Tree. We also briefly discuss the application of this vertex cover methodology to the parametric dual of the Dominating Set problem. This design technique seems to apply to many other FPT problems.

Given a directed graph on n vertices and an integer parameter k, the feedback vertex (arc) set problem asks whether the given graph has a set of k vertices (arcs) whose removal results in an acyclic directed graph. The parameterized complexity of these problems, in the framework introduced by Downey and Fellows, is a long standing open problem in the area. We address these problems in the well studied class of directed graphs called tournaments.While the feedback vertex set problem is easily seen to be fixed parameter tractable in tournaments, we show that the feedback arc set problem is also fixed parameter tractable. Then we address the parametric dual problems (where the k is replaced by ‘all but k’ in the questions) and show that they are fixed parameter tractable in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k vertices (arcs) that forms an acyclic directed subgraph of the graph?

We study the properties of Schnyder’s realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation with height at most $\lceil \frac{15n}{16} \rceil$. This improves the previous best bound of n-1. The drawing can be obtained in linear time. Second, we show that every plane graph G has a straight-line grid embedding on an (n − Δ₀ − 1) × (n − Δ₀ − 1) grid, where Δ₀ is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) × (n-1). This embedding can also be found in O(n) time.

The goals of this survey are to:(1) Motivate the basic notions of parameterized complexity and give some examples to introduce the toolkits of FPT and W-hardness as concretely as possible for those who are new to these ideas.(2) Describe some new research directions, new techniques and challenging open problems in this area.