Applications of a new space-partitioning technique

We present several applications of a recent space-partitioning technique of Chazelle, Sharir, and Welzl (Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 23–33). Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.Work on this paper has been supported by DIMACS, an NSF Science and Technology Center, under Grant STC-88-09684. The second author has been supported by Office of Naval Research Grants N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Suggested research topics in sensitivity and stability analysis for semi-infinite programming problems

We suggest several important research topics for semi-infinite programs whose problem functions and index sets contain parameters that are subject to perturbation. These include optimal value and optimal solution sensitivity and stability properties and penalty function approximation techniques. The approaches proposed are a natural carryover from parametric nonlinear programming, with emphasis on practical applicability and computability.Research supported by National Science Foundation Grant SES 8722504 and Grant ECS-86-19859 and Grant N00014-89-J-1537, Office of Naval Research.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

A deterministic view of random sampling and its use in geometry

The combination of divide-and-conquer and random sampling has proven very effective in the design of fast geometric algorithms. A flurry of efficient probabilistic algorithms have been recently discovered, based on this happy marriage. We show that all those algorithms can be derandomized with only polynomial overhead. In the process we establish results of independent interest concerning the covering of hypergraphs and we improve on various probabilistic bounds in geometric complexity. For example, givenn hyperplanes ind-space and any integerr large enough, we show how to compute, in polynomial time, a simplicial packing of sizeO(r ^d ) which coversd-space, each of whose simplices intersectsO(n/r) hyperplanes.Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8700917. Joel Friedman wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8858788, and this Office of Naval Research under Grant N00014-87-K-0467.A preliminary version of this work has appeared in the proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988). 539–549.     

Pseudo-monotone complementarity problems in Hilbert space

In this paper, some existence results for a nonlinear complementarity problem involving a pseudo-monotone mapping over an arbitrary closed convex cone in a real Hilbert space are established. In particular, some known existence results for a nonlinear complementarity problem in a finite-dimensional Hilbert space are generalized to an infinite-dimensional real Hilbert space. Applications to a class of nonlinear complementarity problems and the study of the post-critical equilibrium state of a thin elastic plate subjected to unilateral conditions are given.This research was partially supported by the National Science Foundation Grant DMS-89-13089, Department of Energy Grant DE-FG03-87-ER-25028, and Office of Naval Research Grant N00014-89-J-1659. The authors would like to express their sincere thanks to Professor S. Schaible, School of Administration, University of California, Riverside, for his helpful suggestions and comments. They also thank the referees for their comments and suggestions that improved this paper substantially.     

The principal pivoting method revisited

The principal pivoting method (PPM) for the linear complementarity problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices.Research partially supported by the National Science Foundation grant DMS-8800589, U.S. Department of Energy grant DE-FG03-87ER25028 and Office of Naval Research grant N00014-89-J-1659.Dedicated to George B. Dantzig on the occasion of his 75th birthday.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

The dimension of suborders of the Boolean lattice

We consider the order dimension of suborders of the Boolean latticeB _n . In particular we show that the suborder consisting of the middle two levels ofB _n dimension at most of 6 log₃ n. More generally, we show that the suborder consisting of levelss ands+k ofB _n has dimensionO(k ² logn).The research of the second author was supported by Office of Naval Research Grant N00014-90-J-1206.The research of the third author was supported by Grant 93-011-1486 of the Russian Fundamental Research Foundation.     

Crossing families

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least . As a consequence we show that such a set possesses a crossing family of size at least , and describe a fast algorithm for finding such a family.Research supported in part by DARPA grant N00014-89-J-1988, Air Force AFOSR-89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC8809648.     

Calculation of bounds on variables satisfying nonlinear inequality constraints

Existing techniques for solving nonconvex programming problems often rely on the availability of lower and upper bounds on the problem variables. This paper develops a method for obtaining these bounds when not all of them are availablea priori. The method is a generalization of the method of Fourier which finds bounds on variables satisfying linear inequality constraints. First, nonlinear inequality constraints are converted to equivalent sets of separable constraints. Generalized variable elimination techniques are used to reduce these to constraints in one variable. Bounds on that variable are obtained and an inductive process yields bounds on the others.Research Sponsored by the Office of Naval Research Grant N00014-89-J-1537.     

The dimension of cycle-free orders

The existence of a four-dimensional cycle-free order is proved. This answers a question of Ma and Spinrad. Two similar problems are also discussed.Research partially supported by Office of Naval Research grant N00014-90-J-1206Research partially supported by the National Science Foundation under grant DMS     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Sensitivity and stability analysis for nonlinear programming

We give a brief overview of important results in several areas of sensitivity and stability analysis for nonlinear programming, focusing initially on qualitative characterizations (e.g., continuity, differentiability and convexity) of the optimal value function. Subsequent results concern quantitative measures, in particular optimal value and solution point parameter derivative calculations, algorithmic approximations, and bounds. Our treatment is far from exhaustive and concentrates on results that hold for smooth well-structured problems.Research supported by National Science Foundation Grant ECS-86-19859 and Grant N00014-89-J-1537 Office of Naval Research.     

Geometric stable distributions in Banach spaces

Geometric stable laws have become an object of attention in recent publications dealing with heavy tailed modeling. Many applications require understanding geometric stable laws on infinite dimensional spaces. This paper studies geometric stable laws on Banach spaces, and their place in the more general family of geometric infinitely divisible laws. Furthermore, we discuss rates of convergence in the domains of attraction of geometric stable laws in Banach spaces.Research was supported by NSF Grant DMS-9103452 and a NATO Scientific Affairs Division Grant CRG 900798. University of California, at Santa Barbara, Santa Barbara, California 93102.Research was supported by ONR Grant N00014-90-J-1287 and United States Israel Binational Science Foundation. School of Operations Research, and Industrial Engineering, Cornell University, Ithaca, New York 14853.     

An analysis of the composite step biconjugate gradient method

Summary The composite step biconjugate gradient method (CSBCG) is a simple modification of the standard biconjugate gradient algorithm (BCG) which smooths the sometimes erratic convergence of BCG by computing only a subset of the iterates. We show that 2×2 composite steps can cure breakdowns in the biconjugate gradient method caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. We also prove a best approximation result for the method. Some numerical illustrations showing the effect of roundoff error are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90-J-1695 and N00014-92-J-1890, the Department of Energy under, contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and ASC 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept. The Chinese University of Hong Kong.     

Triangles in space or building (and analyzing) castles in the air

We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n ^7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.Work on this paper by the first author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, the IBM Corporation, and by a research grant from the NCRD — the Israeli National Council for Research and Development. A preliminary version of this paper has appeared inProc. 4th ACM Symp. on Computational Geometry, Urbana, Illinois, 1988.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.     

Interior-point methods for convex programming

This work is concerned with generalized convex programming problems, where the objective function and also the constraints belong to a certain class of convex functions. It examines the relationship of two basic conditions used in interior-point methods for generalized convex programming—self-concordance and a relative Lipschitz condition—and gives a short and simple complexity analysis of an interior-point method for generalized convex programming. In generalizing ellipsoidal approximations for the feasible set, it also allows a geometrical interpretation of the analysis.This work was supported by a research grant from the Deutsche Forschungsgemeinschaft, and in part by the U.S. National Science Foundation Grant DDM-8715153 and the Office of Naval Research Grant N00014-90-J-1242.On leave from the Institut für Angewandte Mathematik, University of Würzburg, Am Hubland, W-8700 Würzburg, Federal Republic of Germany.