Search

The general block distribution of a matrix is a rectilinear partition of the matrix into orthogonal blocks such that the maximum sum of the elements within a single block is minimized. This corresponds to partitioning the matrix onto parallel processors so as to minimize processor load while maintaining regular communication patterns. Applications of the problem include various parallel sparse matrix computations, compilers for high-performance languages, particle in cell computations, video and image compression, and simulations associated with a communication network. We analyze the performance guarantee of a natural and practical heuristic based on iterative refinement, which has previously been shown to give good empirical results. When p2 is the number of blocks, we show that the tight performance ratio is θ(√p). When the matrix has rows of large cost, the details of the objective function of the algorithm are shown to be important, since a naive implementation can lead to a Ω(p) performance ratio. Extensions to more general cost functions, higher-dimensional arrays, and randomized initial configurations are also considered. In comparison, Khanna et al. have shown the problem to be approximable within O(1) factor [6], while Grigni and Manne have shown it to be NP-hard to approximate within any constant factor less than two [4]. [ABSTRACT FROM AUTHOR]

We investigate a new paradigm of algorithm design for geometric problems that can be termed distribution-sensitive. Our notion of distribution is more combinatorial in nature than spatial. We illustrate this on problems like planar-hulls and 2D-maxima where some of the previously known output-sensitive algorithms are recast in this setting. In a number of cases, the distribution-sensitive analysis yields superior results for the above problems. Moreover these bounds are shown to be tight for a certain class of algorithms. Our approach owes its spirit to the results known for sorting multisets and we exploit this relationship further to derive fast and efficient parallel algorithms for sorting multisets along with the geometric problems. [ABSTRACT FROM AUTHOR]

Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. If the boundaries of two sets in C cross exactly twice, then their intersection points are called regular vertices of the arrangement A(C). Let R(C) denote the set of regular vertices on the boundary of the union of C. We present several bounds on ¦R(C)¦, determined by the type of the sets of C. (i) If each set of C is convex, then ¦R(C)¦ = O(n1.5+ε) for any ε > 0. (ii) If C consists of two collections C1 and C2 where C1 is a collection of n convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and C2 is a collection of polygons with a total of n sides, then ¦R(C)¦=O(n4/3), and this bound is tight in the worst case. (iii) If no further assumptions are made on the sets of C, then we show that there is a positive integer t that depends only on s such that ¦R(C)¦=O(n2−1/t). [ABSTRACT FROM AUTHOR]

This paper is concerned with the efficient computation of additively weighted Voronoi cells for applications in molecular biology. We propose a projection map for the representation of these cells leading to a surprising insight into their geometry. We present a randomized algorithm computing one such cell amidst n other spheres in expected time O(n2 log n). Since the best known upper bound on the complexity such a cell is O(n2), this is optimal up to a logarithmic factor. However, the experimentally observed behavior of the complexity of these cells is linear in n. In this case our algorithm performs the task in expected time O(n log2n). A variant of this algorithm was implemented and performs well on problem instances from molecular biology. [ABSTRACT FROM AUTHOR]

We present a simple and practical algorithm for enumerating the set of cells C of an arrangement of m hyperplanes. For fixed dimension its time complexity is O(m ίddot ¦ C ¦). This is an improvement by a factor of m over the reverse search algorithm by Avis and Fukuda. The algorithm needs little space, is output-sensitive, straightforward to parallelize and the implementation is simple for all dimensions. [ABSTRACT FROM AUTHOR]

A sparse-mesh, which has PUs on the diagonal of a two-dimensional grid only, is a cost effective distributed memory machine. Variants of this machine have been considered before, but none of them is so simple and pure as a sparse-mesh. Various fundamental problems (routing, sorting, list ranking) are analyzed, proving that sparse-meshes have a great potential. The results are extended for higher dimensional sparse-meshes. [ABSTRACT FROM AUTHOR]

In this paper we approach the problem of computing the characteristic polynomial of a matrix from the combinatorial viewpoint. We present several combinatorial characterizations of the coefficients of the characteristic polynomial, in terms of walks and closed walks of different kinds in the underlying graph. We develop algorithms based on these characterizations, and show that they tally with well-known algorithms arrived at independently from considerations in linear algebra. [ABSTRACT FROM AUTHOR]

We present the first randomized upper and lower bounds for online multi-threaded paging as introduced by Feuerstein and Strejilevich de Loma [5]. Our main result is a O(w log k)-competitive algorithm for unfair infinite multi-threaded paging, which is optimal to within a constant factor. We also present algorithms and lower bounds for three other sub-models of multi-threaded paging. [ABSTRACT FROM AUTHOR]

We consider the problem of preemptive non-clairvoyant scheduling on a single machine. In this model a scheduler receives a number of jobs at different times without prior knowledge of the future jobs or the required processing time of jobs that are not yet completed. We want to minimize the total response time, i.e. the sum of times each job takes from its release to completion. One particular algorithm, Balance, always schedules the job that was least processed so far. A comparison of an on-line scheduler running Balance against the optimal off-line shows a very large competitive ratio if both algorithms use machines of the same speed. However, it has been shown if Balance is run on a v times faster machine then the competitive ratio drops to at most 1 + 1/(v−1). This result showed that speed can almost be as good as clairvoyance. We show for v ≥ 2 the competitive ratio of Balance is 2/v. In other words, sufficiently high speed is more powerful than clairvoyance. [ABSTRACT FROM AUTHOR]

Recent experiments demonstrated that local search algorithms (e.g. GSAT) axe able to find satisfying assignments for many "hard" Boolean formulas. However, no non-trivial worst-case upper bounds were proved, although many such bounds of the form 2itαn (α < 1 is a constant) are known for other SAT algorithms, e.g. resolution-like algorithms. In the present paper we prove such a bound for a local search algorithm, namely for CSAT. The class of formulas we consider covers most of DIMACS benchmarks, the satisfiability problem for this class of formulas is NP-complete. [ABSTRACT FROM AUTHOR]

Given an alphabet σ, a (directed) graph G whose edges are weighted and σ-labeled, and a formal language L $$\subseteq$$ σ*, we consider the problem of finding a shortest (simple) path p in G complying with the additional constraint that l(p) ∃ L. Here l(p) denotes the unique word given by concatenating the σ-labels in G along the path p. We consider the computational complexity of the problem for different classes of formal languages (finite, regular, context free and context sensitive), different classes of graphs (unrestricted, grids, treewidth bounded) and different type of path (shortest and shortest simple). A number of variants of the problem are considered and both polynomial time algorithms as well as hardness results (NP-, PSPACE-hardness) are obtained. The hardness and the polynomial time algorithms presented here are a step towards finding such classes of graphs for which polynomial time query evaluation is possible. [ABSTRACT FROM AUTHOR]

This paper addresses memory requirement issues arising in implementations of algorithms on graphs of bounded treewidth. Such dynamic programming algorithms require a large data table for each vertex of a tree-decomposition T of the input graph. We give a lineartime algorithm that finds the traversal order of T minimizing the number of tables stored simultaneously. We show that this minimum value is lower-bounded by the pathwidth of T plus one, and upper bounded by twice the pathwidth of T plus one. We also give a linear-time algorithm finding the depth-first traversal order minimizing the sum of the sizes of tables stored simultaneously. [ABSTRACT FROM AUTHOR]

We prove that the problem to get an inclusion minimal elimination ordering can be solved in linear time for planar graphs. An essential tool is the use of breadth-first search. [ABSTRACT FROM AUTHOR]

The purpose of this talk is to give some idea of the recent progress in obtaining strong, and sometimes tight, inapproximability constants for NP-hard optimization problems. Tight results have been obtained for Max-Ek-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. [ABSTRACT FROM AUTHOR]

Concurrent multicast is a problem of information dissemination from a set of source nodes to a set of destination nodes in a network with cost function: Each source node s needs to multicast a block of data B(s) to the set of destinations. We are interested in protocols for this problem which have minimum communication cost. We consider both the classical case in which any transmitted message can consist of an arbitrary number of data blocks and the case in which each message must consist of exactly one block of data. We show that the problem of determining the minimum cost to perform concurrent multicast is NP-hard under both assumptions. We also give approximation algorithms to efficiently perform concurrent multicast in arbitrary networks. [ABSTRACT FROM AUTHOR]

A Multi Robot Grid System consists of m robots that operate in a set of n ≥ m work locations connected by aisles in a √n × √n grid. From time to time the robots need move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse an edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present an efficient deterministic protocol that allows m=θ (n) robots to visit their target destinations in O (√dn) time, where each robot visits at most d ≤ n targets in any order. We also prove a lower bound that shows that our protocol is optimal. Prior to this paper, no optimal protocols were known for d > 1. For d=1 optimal protocols were known only for m=O (√n), while for m=O (n) only a randomized suboptimal protocol was known. [ABSTRACT FROM AUTHOR]

Two-variable linear programming is a fundamental problem in computational geometry. Sequentially, this problem was solved optimally in linear time by Megiddo and Dyer using the elegant prune-and-search technique. In parallel, the previously best known deterministic algorithm on the EREW PRAM for this problem takes O(log n log log n) time and O(n) work. In this paper, we present a faster parallel deterministic two-variable linear programming algorithm, which takes O(log n log*n) time and O(n) work on the EREW PRAM. Our algorithm is based on an interesting parallel prune-and-search technique, and makes use of new geometric observations which can be viewed as generalizations of those used by Megiddo and Dyer's sequential algorithms. Our parallel prune-and-search technique also leads to efficient EREW PRAM algorithms for other problems, and is likely to be useful in solving more problems. [ABSTRACT FROM AUTHOR]

Comparator networks for constructing binary heaps of size n are presented which have size O(n log log n) and depth O(log n). A lower bound of n log log n — O(n) for the size of any heap construction network is also proven, implying that the networks presented are within a constant factor of optimal. We give a tight relation between the leading constants in the size of selection networks and in the size of heap construction networks. [ABSTRACT FROM AUTHOR]

We present several simple probabilistic data structures for implementing priority queues. We present a data structure called simple bottom-up sampled heap (SBSH), supporting insert in O(1) expected time and delete, delete minimum, decrease key and meld in O(log n) time with high probability. An extension of SBSH called BSH1, supporting insert and meld in O(1) worst case time is presented. This data structure uses a novel "buffering technique" to improve the expected bounds to worst-case bounds. Another extension of SBSH called BSH2, performing insert, decrease key and meld in O(1) amortized expected time and delete and delete minimum in O(log n) time with high probability is also presented. The amortized performance of this data structure is comparable to that of Fibonacci heaps (in probabilistic terms). Moreover, unlike Fibonacci heaps, each operation takes O(log n) time with high probability, making the data structure suitable for real-time applications. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an element of a given rank in a totally ordered set given in a read-only array, using limited extra storage cells. We give new algorithms for various ranges of extra space. Our upper bounds improve the previously known bounds in the range of space s such that s is o(lg2n) and s ≥ clg lg n/lg lg lg n for some constant c. We also give faster algorithms to find small ranks. [ABSTRACT FROM AUTHOR]

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive-each operation produces a new list incorporating the change while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues with catenation that supports all deque operations in constant amortized time. [ABSTRACT FROM AUTHOR]

A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which inserts an element into Q, and DeleteMin, which deletes an element with the minimum priority from Q. In this paper a priority-queue implementation is given which is efficient with respect to the number of block transfers or I/Os performed between the internal and external memories of a computer. Let B and M denote the respective capacity of a block and the internal memory measured in elements. The developed data structure handles any intermixed sequence of Insert and DeleteMin operations such that in every disjoint interval of B consecutive priorityqueue operations at most clogM/BN/M I/Os are performed, for some positive constant c. These I/Os are divided evenly among the operations: if B ≥ clogM/BN/M, one I/O is necessary for every B/(clogM/BN/M)th operation and if B < clogM/BN/M, c/B logM/BN/M I/Os are performed per every operation. Moreover, every operation requires O(log2N) comparisons in the worst case. The best earlier solutions can only handle a sequence of S operations with O(σi=1S 1/B logM/BNi/M) I/Os, where Ni denotes the number of elements stored in the data structure prior to the ith operation, without giving any guarantee for the performance of the individual operations. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, we seek two squares whose center points belong to P, their union contains P, and the area of the larger square is minimal. We present efficient algorithms for three variants of this problem: In the first the squares axe axis parallel, in the second they are free to rotate but must remain parallel to each other, and in the third they are free to rotate independently. [ABSTRACT FROM AUTHOR]

We study the consequences of two of the realistic input models proposed in the literature, namely unclutteredness and small simple-cover complexity, for the motion planning problem. We show that the complexity of the free space of a bounded-reach robot with f degrees of freedom is O(nf/2) in the plane, and O(n2f/3) in three dimensions, for both uncluttered environments and environments of small simple-cover complexity. We also give an example showing that these bounds are tight in the worst case. Our bounds fit nicely between the θ(nf) bound for the maximum free-space complexity in the general case, and the θ(n) bound for low-density environments. [ABSTRACT FROM AUTHOR]

Let D be a connected region inside a simple polygon, P. We define the angle hull, $$\mathcal{A}\mathcal{H}$$ (D), of D to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of $$\mathcal{A}\mathcal{H}$$ (D) cannot exceed the perimeter of the relative convex hull of D by more than a factor of 2. A special case occurs when P equals the full plane. Here we prove a bound of π/2. Both bounds are tight, and corresponding results are obtained for any other angle. [ABSTRACT FROM AUTHOR]

Given a set S of n colored line segments in ℝ2 that may intersect only in endpoints. Let c(u) denote the color of a line segment u ∃ S chosen from χ ≤ n different colors. A line segment v ∃ S is a visible nearest foreign neighbor of u ∃ S if v is a nearest foreign neighbor of u in S, i.e. c(u) ≠ c(v) and no segment with a color different from c(u) is closer to u than v, and if there exist points u' ∃ u and v' ∃ v realizing the distance between u and v that are visible for each other, i.e. the open segment connecting u' and v' is not intersected by an open line segment in S. We present the first optimal θ(n log n) algorithm that computes for each line segment u ∃ S all its visible nearest foreign neighbors. The algorithm finds applications in polygon arrangement analysis, VLSI design rule checking and GIS. [ABSTRACT FROM AUTHOR]

In this paper we consider the following bin packing problem with conflicts. Given a set of items V={1..., n} with sizes s1..., sn ∃ (0,1] and a conflict graph G=(V,E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j') ∃ E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem. We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ε) of optimal, and has a running time polynomial both in n and 1/ε. [ABSTRACT FROM AUTHOR]

Let P be a simple polyhedron, possibly non-convex, whose boundary is composed of n triangular faces, and in which each face has an associated positive weight. The cost of travel through each face is the distance traveled multiplied by the face's weight. We present an ε-approximation algorithm for computing a weighted shortest path on P, i.e. the ratio of the length of the computed path with respect to the length of an optimal path is bounded by (1 + ε), for a given ε > 0.We give a detailed analysis to determine the exact constants for the approximation factor. The running time of the algorithm is O(mn log mn + nm2). The total number of Steiner points, m, added to obtain the approximation depends on various parameters of the given polyhedron such as the length of the longest edge, the minimum angle between any two adjacent edges of P and the minimum distance from any vertex to the boundary of the union of its incident faces and the ratio of the largest (finite) to the smallest face weights of P. Lastly, we present an approximation algorithm with an improved running time of O(mn log mn), at the cost of trading off the constants in the path accuracy. Our results present an improvement in the dependency on the number of faces, n, to the recent results of Mata and Mitchell [10] by a multiplicative factor of n2/log n, and to that of Mitchell and Papadimitriou [11] by a factor of n7. [ABSTRACT FROM AUTHOR]

Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a city street network for emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to traffic congestion the traversal time on links changes with time. Very often, we have estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) as centers, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results for the K-center problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good time-invariant solutions. [ABSTRACT FROM AUTHOR]

Regarding members of a class of graphs as values of algebraic expressions allows definition of a congruence such that the given class is the union of some of the equivalence classes. In many cases this congruence has a finite number of equivalence classes. Such a congruence can be used to generate a reduction system that decides the class membership in linear time. However, a congruence for a given problem is often difficult to determine. We describe a technique that produces an algebra and a congruence relation on its carrier for some classes of graphs. Our technique builds on considering possible representations of the generated graphs as graphs of the desired class. By introduction of a labeling describing the "most parsimonious" such representations, we can work with small labeled graphs instead of large unlabeled ones, and some of the case analysis can be delegated to the algebraic machinery used. The congruence relation is subsequently used to construct a labeled graph reduction system based on a reduction system recognizing a larger class than the one sought. [ABSTRACT FROM AUTHOR]