A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

Strongly polynomial dual simplex methods for the maximum flow problem

This paper presents dual network simplex algorithms that require at most 2nm pivots and O(n ² m) time for solving a maximum flow problem on a network ofn nodes andm arcs. Refined implementations of these algorithms and a related simplex variant that is not strictly speaking a dual simplex algorithm are shown to have a complexity of O(n ³). The algorithms are based on the concept of apreflow and depend upon the use of node labels that are underestimates of the distances from the nodes to the sink node in the extended residual graph associated with the current flow. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research was supported by NSF Grants DMS 91-06195, DMS 94-14438 and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.Research was supported by NSF Grant CDR 84-21402 at Columbia University.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Constructing arrangements optimally in parallel

We give two optimal parallel algorithms for constructing the arrangement ofn lines in the plane. The first nethod is quite simple and runs inO(log² n) time usingO(n ²) work, and the second method, which is more sophisticated, runs inO(logn) time usingO(n ²) work. This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of an -pseudocutting. Our results immediately imply that the arrangement ofn hyperplanes in ^d inO(logn) time usingO(n ^d) work, for fixedd, can be optimally constructed. Our algorithms are for the CREW PRAM.This research was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

Primal separation for 0/1 polytopes

 The 0/1 primal separation problem is: Given an extreme point xˉ of a 0/1 polytope P and some point x ^*, find an inequality which is tight at xˉ, violated by x ^* and valid for P or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for P. We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. In contrast, the known standard separation method relies on an explicit minimum odd cut algorithm. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. Received: August 20, 2001 / Accepted: April 2002 Published online: December 9, 2002 RID="⋆" ID="⋆" This research was developed while the author was on leave at the Istituto di Analisi dei Sistemi ed Informatica, Viale Manzoni 30, 00185 Roma, supported by the project TMR-DONET nr. ERB FMRX-CT98-0202 of the European Union. Mathematics Subject Classification (2000): 90C10, 90C60, 90C57     

Global minimum test problem construction

A method is presented for the construction of test problems for which the global minimum point is known.Given a bounded convex polyhedron inR ⁿ , and a selected vertex, a concave quadratic function is constructed which attains its global minimum at the selected vertex. In general, this function will also have many other local minima.This research was supported in part by NSF Grant MCS 81-01214.     

Lower bounds on moving a ladder in two and three dimensions

It is shown that (n ²) distinct moves may be necessary to move a line segment (a ladder) in the plane from an initial to a final position in the presence of polygonal obstacles of a total ofn vertices, and that (n ⁴) moves may be necessary for the same problem in three dimensions. These two results establish lower bounds on algorithms that solve the motion-planning problems by listing the moves of the ladder. The best upper bounds known areO(n ² logn) in two dimensions, andO(n ⁵ logn) in three dimensions.This work was partially supported by NSF Grants DCR-83-51468 and grants from Martin Marietta, IBM, and General Motors.     

Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Visibility graphs of staircase polygons and the weak Bruhat order,I: From visibility graphs to maximal chains

The recognition problem for visibility graphs of simple polygons is not known to be in NP, nor is it known to be NP-hard. It is, however, known to be inPSPACE. Further, every such visibility graph can be dismantled as a sequence of visibility graphs of convex fans. Any nondegenerated configuration ofn points can be associated with amaximal chain in the weak Bruhat order of the symmetric groupS _n . The visibility graph ofany simple polygon defined on this configuration is completely determined by this maximal chain via a one-to-one correspondence between maximal chains andbalanced tableaux of a certain shape. In the case of staircase polygons (special convex fans), we define a class of graphs calledpersistent graphs and show that the visibility graph of a staircase polygon is persistent. We then describe a polynomial-time algorithm that recovers a representative maximal chain in the weak Bruhat order from a given persistent graph, thus characterizing the class of persistent graphs. The question of recovering a staircase polygon from a given persistent graph, via a maximal chain, is studied in the companion paper [4]. The overall goal of both papers is to offer a characterization of visibility graphs, of convex fans. The research of J. Abello was supported by NSF Grants Nos. DCR 8603722 and DCR 8896281. This research was done while K. Kumar was at the Department of Computer Science, Texas A & M University.     

AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.This work was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

An efficient algorithm for the “stable roommates” problem

The stable marriage problem is that of matching n men and n women, each of whom has ranked the members of the opposite sex in order of preference, so that no unmatched couple both prefer each other to their partners under the matching. At least one stable matching exists for every stable marriage instance, and efficient algorithms for finding such a matching are well known. The stable roommates problem involves a single set of even cardinality n, each member of which ranks all the others in order of preference. A stable matching is now a partition of this single set into n/2 pairs so that no two unmatched members both prefer each other to their partners under the matching. In this case, there are problem instances for which no stable matching exists. However, the present paper describes an O(n²) algorithm that will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching.     

Almost tight upper bounds for the single cell and zone problems in three dimensions

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Israel Science Fund administered by the Israeli Academy of Sciences.     

Hammersley's interacting particle process and longest increasing subsequences

Summary In a famous paper [8] Hammersley investigated the lengthL _n of the longest increasing subsequence of a randomn-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly “soft” arguments that limn ^′1/2 EL _n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. Research supported by NSF Grant MCS 92-24857 and the Miller Institute for Basic Research in Science Research supported by NSF Grant DMS92-04864     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.