Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines

We develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms.     

Optimal parallel algorithms for rectilinear link-distance problems

We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute:

1. Minimum réctilinear link paths, or shortest paths in theL ₁ metric from any point inP to all vertices ofP.
2. Minimum rectilinear link paths from any segment insideP to all vertices ofP.
3. The rectilinear window (histogram) partition ofP.
4. Both covering radii and vertex intervals for any diagonal ofP.
5. A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor).

Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which usedO(n logn) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.     

Approximate algorithms for some generalized knapsack problems

In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.The research of R. Cole was supported in part by NSF Grants CCR-8702271, CCR-8902221, and CCR-8906949, by ONR Grant N00014-85-K-0046, and by a John Simon Guggenheim Memorial Foundation fellowship. M. T. Goodrich's research was supported by the National Science Foundation under Grant CCR-8810568 and by the National Science Foundation and DARPA under Grant CCR-8908092.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.     

Space and time optimal algorithms for a class of rectangle intersection problems

The intersection problem for a subclass of rectangles called r-rectangles is investigated and reduced to the balanced batched r(estricted)-range searching problem as well as to the balanced batched inverse r-range searching problem. Simple algorithms for these problems are given which are space and time optimal. The algorithm given for the balanced batched r-range searching problem leads to a new algorithm for the all-points ECDF problem in 2-space which is simple and optimal. Again, the balanced batched r-range searching algorithm is combined with a known algorithm for batched range searching problems, leading to a new algorithm for the rectangle intersection problem which is space and time optimal in the worst case when the given set of rectangles contains a much higher proportion of r-rectangles.     

General approximation algorithms for some arithmetical combinatorial problems

A general approximation technique for a large class of NP-hard optimization problems which involve arithmetic calculations is given. This technique guarantees a worst case relative error smaller than ε in time which is polynomial both in the size of the problem instance and 1/ε. It is also shown that problems in that class which are not approximable by this technique are not approximable in polynomial time at all, provided P ≠ NP, and hence this technique is the most general approximation technique applicable to this class.     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

Space efficient algorithms for some graph theoretical problems

Summary We present space-efficient-O(log² n)-deterministic algorithms for some graph theoretical problems such as planarity testing, producing a plane embedding, finding minimum cost spanning trees, obtaining the connected, biconnected and triconnected components of a graph. Previous planarity algorithms used (n) space. Several algorithms are based on a space-efficient matrix inversion method. The same bounds hold for uniform circuit depth.Research partially supported by NSF grants No. MCS 79-05006 and MCS 78-27600.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.     

Optimal algorithms for sensitivity analysis in associative multiplication problems

We consider efficient ways of determining the sensitivity of a product to changes in individual factors. The task is motivated by several interesting combinatorial and numeric problems which can be given a unified formulation as the problem of finding the (associative) product of N objects. Both deterministic and probabilistic changes to the factors are considered. Algorithms for two kinds of deterministic variation schemes are considered. Nontrivial lower bounds are obtained which demonstrate the algorithms to be optimal. For probabilistic choice of the parameter to be varied, it is shown that optimal ordered binary search trees or Huffman trees determine the optimal strategies. A number of unsolved are posed.     

Optimal algorithms for rectangle problems on a mesh-connected computer

In this paper, Mesh-Connected Computer (MCC) algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, we describe MCC algorithms for determining the following properties: (i) the area of the logic “OR” of these rectangles (i.e., the area of the region covered by at least one rectangle); (ii) the area of the union of pairwise “AND” of the rectangles (i.e., the area of the region covered by two or more rectangles); (iii) the largest number of rectangles that overlap (this solves the fixed-size rectangle placement problem, i.e., given a set of planar points and a rectangle, find a placement of the rectangle in the plane so that the number of points covered by the rectangle is maximal); (iv) the minimum separation between any pair of a set of nonoverlapping rectangles. All these algorithms can be implemented on a 2√n × 2√n MCC in O(√n) time which is optimal. The algorithms compare favorably with the known sequential algorithms that have O(n log n) time complexity.     

On some union and intersection problems for polygons with fixed orientations

Objects with fixed orientations play an important role in many application areas, for instance VLSI design. Problems involving only rectilinearly oriented (rectangular) objects, as a simplest case, have been studied with the VLSI design application in mind. These objects can be transistors, cells or macros. In reality, they are more suitably represented by polygons rather than just rectangles. In this note we describe how to perform a general decomposition of a set of polygons with fixed orientations in order to solve various computational geometry problems which are important in VLSI design. The decomposition is very simple and efficiently computable, and it allows the subsequent application of algorithms for the rectilinear case, leading to some very efficient and some optimal solutions. We illustrate the technique in detail at the problem of finding the connected components of a set of polygons, for which we derive an optimal solution. The wide applicability of the method is then demonstrated at the problem of finding all pairs of intersecting polygons, yielding an optimal solution.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T. J. Watson Research Center.     

Efficient algorithms for consensus string problems minimizing both distance sum and radius

The consensus (string) problem is finding a representative string, called a consensus, of a given set S of strings. In this paper we deal with consensus problems considering both distance sum and radius, where the distance sum is the sum of (Hamming) distances from the strings in S to the consensus and the radius is the longest (Hamming) distance from the strings in S to the consensus. Although there have been results considering either distance sum or radius, there have been no results considering both, to the best of our knowledge.We present the first algorithms for two consensus problems considering both distance sum and radius for three strings: one problem is to find an optimal consensus minimizing both distance sum and radius. The other problem is to find a bounded consensus such that the distance sum is at most s and the radius is at most r for given constants s and r. Our algorithms are based on characterization of the lower bounds of distance sum and radius, and thus they solve the problems efficiently. Both algorithms run in linear time.     

Optimal algorithms for dissemination of information in some interconnection networks

The problems of gossiping and broadcasting in one-way communication mode are considered for some prominent families of graphs. The complexity is measured as the number of communication rounds in the gossip and broadcast algorithms. The main result of the paper is the precise estimation of the gossip-problem complexity in cycles. To obtain this result a new combinatorial analysis of gossiping in cycles is developed. This analysis leads to an optimal lower bound on the number of rounds, and also to the design of an optimal algorithm for gossiping in cycles. The optimal algorithm for gossiping is later used to design new, effective algorithms for gossiping in important families of interconnection networks (cube connected cycles, butterfly networks). Furthermore, a new, effective algorithm for broadcasting in shuffle-exchange networks is developed.On leave from Comenius University, Bratislava, Czechoslovakia.     

Optimal parallel algorithms for problems modeled by a family ofintervals

A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. The authors develop computational tools and show how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems, including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all the algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation     

Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some application. This paper considers semi-online problems on identical machines with inexact partial information. Three problems are considered, where we know in advance that the optimal value, or the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter r ∈[1, ∞). We establish for which r the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal preemptive semi-online algorithms are then obtained. Research supported by Natural Science Foundation of China (10671177) and Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in proceedings of ISAAC’05.     

Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio and job processing time ratio for the first problem, and an optimal semi-online algorithm for every machine speed ratio for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).     

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O(N ⁴) processors. Here we show that these problems can be solved in constant time using only O(N ²) processors on the BSR model (N is the number of vertices of the graph G). Therefore, our algorithms are more work-efficient. These new results suggest that many other problems in graph theory can be solved in constant time using the BSR model.